Nordhaus–Gaddum-type Theorems for decompositions into many parts
✍ Scribed by Zoltan Füredi; Alexandr V. Kostochka; Riste Škrekovski; Michael Stiebitz; Douglas B. West
- Publisher
- John Wiley and Sons
- Year
- 2005
- Tongue
- English
- Weight
- 165 KB
- Volume
- 50
- Category
- Article
- ISSN
- 0364-9024
No coin nor oath required. For personal study only.
✦ Synopsis
Abstract
A k‐decomposition (G~1~,…,G~k~) of a graph G is a partition of its edge set to form k spanning subgraphs G~1~,…,G~k~. The classical theorem of Nordhaus and Gaddum bounds χ(G~1~) + χ(G~2~) and χ(G~1~)χ(G~2~) over all 2‐decompositions of K~n~. For a graph parameter p, let p(k;G) denote the maximum of $\sum _{i=1}^k p(G_i)$ over all k‐decompositions of the graph G. The clique number ω, chromatic number χ, list chromatic number χℓ, and Szekeres–Wilf number σ satisfy ω(2;K~n~) = χ(2;K~n~) = χℓ(2;K~n~) = σ(2;K~n~) = n + 1. We obtain lower and upper bounds for ω(k;K~n~), χ(k;K~n~), χℓ(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. © 2005 Wiley Periodicals, Inc. J Graph Theory