Nordhaus-Gaddum-type theorems for decompositions into many parts

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 chi(G(1)) + chi(G(2)) and chi(G(1))chi(G(2)) over all 2-decompositions of K, For a graph parameter p, let p(k;G) denote the maximum of Sigma(k)(i=1) p(G(i)) over all k-decompositions of the graph G. The clique number omega, chromatic number chi, list chromatic number chi(l), and Szekeres-Wilf number sigma satisfy omega(2;K-n) = chi(2;K-n) = X-l(2;K-n) = sigma(2;K-n) = n + 1. We obtain lower and upper bounds for omega(k;K-n), chi(k;K-n), chi(l)(k;K-n), and alpha(k;K-n). The last three behave differently for large k. We also obtain lower and upper bounds for the maximum of X(k; G) over all graphs embedded on a given surface. (c) 2005 Wiley Periodicals, Inc.