Colouring random subgraphs

2023/12/13 by Bukh, Boris, Krivelevich, Michael, Narayanan, Bhargav
Mathematics · #05C15 #05C80 #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Probability (math.PR)

paper · pdf · doi:10.48550/arxiv.2312.08340

openalex publication_date 2023/12/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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).

Related

• Colouring random graphs: Tame colourings
• On the chromatic number of random d-regular graphs
• Clique colouring of binomial random graphs
• On the non-3-colourability of random graphs
• An algorithmic framework for colouring locally sparse graphs