Tight Bounds on the Clique Chromatic Number
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 $\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.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
0
References
0
Citations
NaN
KQI