Tight Bounds on the Clique Chromatic Number

Abstract

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 $\Delta$ has clique chromatic number $O\left(\frac{\Delta }{\log \Delta }\right)$. We obtain as a corollary that every $n$-vertex graph has clique chromatic number $O\left(\sqrt{\frac{n}{\log n}}\right)$. Both these results are tight.

v2: revised following referees' comments

References in corpus (2)

• Perfect graphs of arbitrarily large clique-chromatic number
• Clique colouring of binomial random graphs

Cited by in corpus (1)

• The jump of the clique chromatic number of random graphs