Bounds on chromatic numbers of multiple factors of a complete graph
Ján Plesnı́k · Journal of Graph Theory · 1978
Abstract Bounds on the sum and product of the chromatic numbers of n factors of a complete graph of order p are shown to exist. The well‐known theorem of Nordhaus and Gaddum solves the problem for n = 2. Strict lower and some upper bounds for any n and strict upper bounds for n = 3 are given. In particular, the sum of the chromatic numbers of three factors is between 3 p 1/3 and p + 3 and the product is between p and [( p + 3)/3] 3 .