Nordhaus-Gaddum Theorems for Multifactor Decompositions

A Nordhaus-Gaddum theorem states bounds on \(p\left (G\right )+p\left (\overline {G}\right )\) and \(p\left (G\right )\cdot p\left (\overline {G}\right )\) for some graph parameter \(p\left (G\right )\) . Viewing \(\left \{ G,\overline {G}\right \} \) as a decomposition of \(K_{n}\) allows us to generalize these theorems to decompositions of \(K_{n}\) with more than two factors. We determine the sum upper bound for independence number, domination number, edge independence number, maximum degree, edge chromatic number, and clique number. We also determine the extremal decompositions for the product lower bound for chromatic number.