On the chromatic number of random triangle-free graphs

2025/09/01 by Mizgerd, Clayton, Perkins, Will, Wang, Yuzhou
#Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.2509.01376

Abstract

We study the chromatic number of typical triangle-free graphs with Θ( n^3/2 (log n)^1/2 ) edges and establish the width of the scaling window for the transitions from χ= 3 to χ= 4 and from χ= 4 to χ= 5. The transition from 3- to 4-colorability has scaling window of width Θ(n^4/3 (log n)^-1/3). To prove this, we show a high probability equivalence of the 3-colorability of a random triangle-free graph at this density and the satisfiability of an instance of bipartite random 2-SAT, for which we establish the width of the scaling window following the techniques of Bollobás, Borgs, Chayes, Kim, and Wilson. The transition from 4- to 5-colorability has scaling window of width Θ(n^3/2 (log n)^-1/2). To prove this, we show a high probability equivalence of the 4-colorability of a random triangle-free graph at this density and the simultaneous 2-colorability of two independent Erdős--Rényi random graphs. For this transition, we also establish the limiting probability of 4-colorability inside the scaling window.

Citations

• Asymptotics for the number of bipartite graphs with fixed surplus
• Searching for (sharp) thresholds in random structures: where are we now?
• On the evolution of structure in triangle-free graphs
• Threshold phenomena for random discrete structures
• Exact enumeration of satisfiable 2-SAT formulae
• Component behaviour and excess of random bipartite graphs near the critical point
• A critical point for random graphs with a given degree sequence

Related

• A Coloring Algorithm for Triangle-Free Graphs
• On the non-3-colourability of random graphs
• The Chromatic Number of Random Regular Graphs
• On the evolution of structure in triangle-free graphs
• Conflict-free coloring of graphs