Chromatic thresholds in sparse random graphs

Abstract

The chromatic threshold ${\delta }_{\chi }(H,p)$ of a graph $H$ with respect to the random graph $G(n,p)$ is the infimum over $d>0$ such that the following holds with high probability: the family of $H$-free graphs $G\subset G(n,p)$ with minimum degree $\delta (G)\ge dpn$ has bounded chromatic number. The study of ${\delta }_{\chi }(H):={\delta }_{\chi }(H,1)$ was initiated in 1973 by Erdős and Simonovits. Recently ${\delta }_{\chi }(H)$ was determined for all graphs $H$. It is known that ${\delta }_{\chi }(H,p)={\delta }_{\chi }(H)$ for all fixed $p\in (0,1)$, but that typically ${\delta }_{\chi }(H,p)\ne {\delta }_{\chi }(H)$ if $p=o(1)$. Here we study the problem for sparse random graphs. We determine ${\delta }_{\chi }(H,p)$ for most functions $p=p(n)$ when $H\in \{K_3,C_5\}$, and also for all graphs $H$ with $\chi (H)\notin \{3,4\}$.

23 pages, 1 figure; accepted to Random Structures and Algorithms