Tight Bounds on the Clique Chromatic Number

DOI10.37236/9659arXiv2006.11353MaRDI QIDQ6343313

Bruce Reed, Gwenaël Joret, Michiel Smid, Piotr Micek

Publication date: 19 June 2020

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 $Oleft(fracDeltalogDeltaight)$. We obtain as a corollary that every $n$-vertex graph has clique chromatic number $Oleft(sqrtfracnlognight)$. Both these results are tight.

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

This page was built for publication: Tight Bounds on the Clique Chromatic Number

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6343313)