Nordhaus-gaddum-type theorems for decompositions into many parts

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

Research output: Contribution to journalArticle

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.

Original languageEnglish (US)
Pages (from-to)273-292
Number of pages20
JournalJournal of Graph Theory
Volume50
Issue number4
DOIs
StatePublished - Dec 2005

Keywords

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

ASJC Scopus subject areas

  • Geometry and Topology

Fingerprint Dive into the research topics of 'Nordhaus-gaddum-type theorems for decompositions into many parts'. Together they form a unique fingerprint.

  • Cite this