Nordhaus–Gaddum‐type Theorems for decompositions into many parts
Nordhaus–Gaddum‐type Theorems for decompositions into many parts
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 ) …