The clique chromatic number of sparse random graphs

ACO Student Seminar
Friday, April 22, 2022 - 1:00pm for 1 hour (actually 50 minutes)
Skiles 254
Manuel Fernandez – Mathematics, Georgia Tech –
Abhishek Dhawan

Please Note: Streaming online at

The clique chromatic number of a graph is the smallest number of colors in a vertex coloring so that no inclusion-maximal clique is monochromatic (ignoring isolated vertices). 

For the binomial random graph G_{n,p} the clique chromatic number has been studied in a number of works since 2016, but for sparse edge-probabilities in the range n^{-2/5} \ll p \ll 1 even the order of magnitude remained a technical challenge.

Resolving open problems of Alon and Krivelevich as well as Lichev, Mitsche and Warnke, we determine the clique chromatic number of the binomial random graph G_{n,p} in most of the missing regime: we show that it is of order (\log n)/p for edge-probabilities n^{-2/5+\eps} \ll p \ll n^{-1/3} and n^{-1/3+\eps} \ll p \ll 1, for any constant \eps > 0.

Perhaps surprisingly for a result about random graphs, a key ingredient in the proof is an application of the probabilistic method (that hinges on careful counting and density arguments).

This talk is based on joint work with Lutz Warnke.