On the Chromatic Number of Random Triangle‐Free Graphs

ABSTRACT We study the chromatic number of typical triangle‐free graphs with edges and establish the width of the scaling window for the transitions from to and from to . The transition from 3‐ to 4‐colorability has scaling window of width . 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 . 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.