Nordhaus-gaddum-type theorems for decompositions into many parts

Zoltan Füredi; Alexandr V. Kostochka; Riste Škrekovski; Michael Stiebitz; Douglas B. West

doi:10.1002/jgt.20113

Nordhaus-gaddum-type theorems for decompositions into many parts

Zoltan Füredi, Alexandr V. Kostochka, Riste Škrekovski, Michael Stiebitz, Douglas B. West

Mathematics

Research output: Contribution to journal › Article › peer-review

Abstract

A k-decomposition (G₁,..., G_k) of a graph G is a partition of its edge set to form k spanning subgraphs G₁,..., G _k. The classical theorem of Nordhaus and Gaddum bounds χ(G ₁) + χ(G₂) and χ(G₁)χ(G ₂z) over all 2-decompositions of k_n. For a graph parameter p, let p(k;G) denote the maximum of Σ_i=1^k p(G_i/) over all k-decompositions of the graph G. The clique number Ω, chromatic number χ, list chromatic number χ_l, and Szekeres-Wilf number σ satisfy ω(2;K_n) = χ(2;K _n) = χ_l(2;K_n) = σ(2;K_n) = n + 1. We obtain lower and upper bounds for ω(k;K _n),χ(k;K_n),χ_l(k;K_n), and σ(k;K_n). The last three behave differently for large k. We also obtain lower and upper bounds for the maximum of χ(k;G) over all graphs embedded on a given surface.

Original language	English (US)
Pages (from-to)	273-292
Number of pages	20
Journal	Journal of Graph Theory
Volume	50
Issue number	4
DOIs	https://doi.org/10.1002/jgt.20113
State	Published - Dec 2005

Keywords

Chromatic number
Coloring number
Graph decomposition
List chromatic number
Nordhaus-Gaddum Theorem
Surface embedding

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Geometry and Topology

Online availability

10.1002/jgt.20113

Library availability

Discover UIUC Full Text

Cite this

@article{0a64df70d1aa41aba07f332ce3a7d92e,

title = "Nordhaus-gaddum-type theorems for decompositions into many parts",

abstract = "A k-decomposition (G1,..., Gk) of a graph G is a partition of its edge set to form k spanning subgraphs G1,..., G k. The classical theorem of Nordhaus and Gaddum bounds χ(G 1) + χ(G2) and χ(G1)χ(G 2z) over all 2-decompositions of kn. For a graph parameter p, let p(k;G) denote the maximum of Σi=1k p(Gi/) over all k-decompositions of the graph G. The clique number Ω, chromatic number χ, list chromatic number χl, and Szekeres-Wilf number σ satisfy ω(2;Kn) = χ(2;K n) = χl(2;Kn) = σ(2;Kn) = n + 1. We obtain lower and upper bounds for ω(k;K n),χ(k;Kn),χl(k;Kn), and σ(k;Kn). The last three behave differently for large k. We also obtain lower and upper bounds for the maximum of χ(k;G) over all graphs embedded on a given surface.",

keywords = "Chromatic number, Coloring number, Graph decomposition, List chromatic number, Nordhaus-Gaddum Theorem, Surface embedding",

author = "Zoltan F{\"u}redi and Kostochka, {Alexandr V.} and Riste {\v S}krekovski and Michael Stiebitz and West, {Douglas B.}",

year = "2005",

month = dec,

doi = "10.1002/jgt.20113",

language = "English (US)",

volume = "50",

pages = "273--292",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley-Liss Inc.",

number = "4",

}

TY - JOUR

T1 - Nordhaus-gaddum-type theorems for decompositions into many parts

AU - Füredi, Zoltan

AU - Kostochka, Alexandr V.

AU - Škrekovski, Riste

AU - Stiebitz, Michael

AU - West, Douglas B.

PY - 2005/12

Y1 - 2005/12

N2 - A k-decomposition (G1,..., Gk) of a graph G is a partition of its edge set to form k spanning subgraphs G1,..., G k. The classical theorem of Nordhaus and Gaddum bounds χ(G 1) + χ(G2) and χ(G1)χ(G 2z) over all 2-decompositions of kn. For a graph parameter p, let p(k;G) denote the maximum of Σi=1k p(Gi/) over all k-decompositions of the graph G. The clique number Ω, chromatic number χ, list chromatic number χl, and Szekeres-Wilf number σ satisfy ω(2;Kn) = χ(2;K n) = χl(2;Kn) = σ(2;Kn) = n + 1. We obtain lower and upper bounds for ω(k;K n),χ(k;Kn),χl(k;Kn), and σ(k;Kn). The last three behave differently for large k. We also obtain lower and upper bounds for the maximum of χ(k;G) over all graphs embedded on a given surface.

AB - A k-decomposition (G1,..., Gk) of a graph G is a partition of its edge set to form k spanning subgraphs G1,..., G k. The classical theorem of Nordhaus and Gaddum bounds χ(G 1) + χ(G2) and χ(G1)χ(G 2z) over all 2-decompositions of kn. For a graph parameter p, let p(k;G) denote the maximum of Σi=1k p(Gi/) over all k-decompositions of the graph G. The clique number Ω, chromatic number χ, list chromatic number χl, and Szekeres-Wilf number σ satisfy ω(2;Kn) = χ(2;K n) = χl(2;Kn) = σ(2;Kn) = n + 1. We obtain lower and upper bounds for ω(k;K n),χ(k;Kn),χl(k;Kn), and σ(k;Kn). The last three behave differently for large k. We also obtain lower and upper bounds for the maximum of χ(k;G) over all graphs embedded on a given surface.

KW - Chromatic number

KW - Coloring number

KW - Graph decomposition

KW - List chromatic number

KW - Nordhaus-Gaddum Theorem

KW - Surface embedding

UR - http://www.scopus.com/inward/record.url?scp=30544438238&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=30544438238&partnerID=8YFLogxK

U2 - 10.1002/jgt.20113

DO - 10.1002/jgt.20113

M3 - Article

AN - SCOPUS:30544438238

SN - 0364-9024

VL - 50

SP - 273

EP - 292

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 4

ER -

Nordhaus-gaddum-type theorems for decompositions into many parts

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this