Tight Bounds on the Clique Chromatic Number - Joret, Gwenaël; Micek, Piotr; Reed, Bruce; Smid, Michiel (The Electronic Journal of Combinatorics, 2021)
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(Δ Δ). We obtain as a corollary that every n-vertex graph has clique chromatic number O(n n ). Both these results are tight.