Tight Bounds on The Clique Chromatic Number
share
The clique chromatic number of a graph is the minimum number of colours needed to colour its vertices so that no inclusion-wise maximal clique which is not an isolated vertex is monochromatic. We show that every graph of maximum degree Δ has clique chromatic number O(Δ/log Δ). We obtain as a corollary that every n-vertex graph has clique chromatic number O(√(n/log n)). Both these results are tight.
READ FULL TEXT
