Nordhaus–Gaddum‐type Theorems for decompositions into many parts

DOI10.1002/jgt.20113zbMath1078.05068OpenAlexW4239590384MaRDI QIDQ5711696

Douglas B. West, Riste Škrekovski, Michael Stiebitz, Zoltan Fueredi, Alexandr V. Kostochka

Publication date: 8 December 2005

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/jgt.20113

zbMATH Keywords

chromatic numberlist chromatic numbercoloring numbersurface embedding

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15)

Related Items

NORDHAUS–GADDUM-TYPE THEOREM FOR DIAMETER OF GRAPHS WHEN DECOMPOSING INTO MANY PARTS ⋮ Ramsey numbers for degree monotone paths ⋮ Maximum size of digraphs with some parameters ⋮ Nordhaus-Gaddum type result for the matching number of a graph ⋮ Extremal decompositions for Nordhaus-Gaddum theorems ⋮ Nordhaus-Gaddum for treewidth ⋮ Multiple factor Nordhaus-Gaddum type results for domination and total domination ⋮ Nordhaus-Gaddum bounds for total domination ⋮ Nordhaus-Gaddum-type theorem for Wiener index of graphs when decomposing into three parts ⋮ Inequalities for the first-fit chromatic number ⋮ Nordhaus-gaddum type inequalities for tree covering numbers on unitary cayley graphs of finite rings ⋮ Nordhaus-Gaddum inequalities for the fractional and circular chromatic numbers ⋮ A map colour theorem for the union of graphs ⋮ The Erdős-Hajnal conjecture for three colors and triangles ⋮ Improving a Nordhaus-Gaddum type bound for total domination using an algorithm involving vertex disjoint stars

Cites Work

• Short Proof of a Map-Colour Theorem
• Choice Numbers of Graphs: a Probabilistic Approach
• A Six Color Problem
• Unnamed Item

This page was built for publication: Nordhaus–Gaddum‐type Theorems for decompositions into many parts