Colouring random subgraphs
Boris Bukh, Michael Krivelevich, Bhargav P. Narayanan · Combinatorics Probability Computing · 2025
Abstract We study several basic problems about colouring the $p$ -random subgraph $G_p$ of an arbitrary graph $G$ , focusing primarily on the chromatic number and colouring number of $G_p$ . In particular, we show that there exist infinitely many $k$ -regular graphs $G$ for which the colouring number (i.e., degeneracy) of $G_{1/2}$ is at most $k/3 + o(k)$ with high probability, thus disproving the natural prediction that such random graphs must have colouring number at least $k/2 - o(k)$ .