Tight Bounds on The Clique Chromatic Number

06/19/2020
by   Gwenaël Joret, et al.
0

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

Please sign up or login with your details

Forgot password? Click here to reset