Tight bounds on the clique chromatic number (Q820840)

Summary: 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.