On the Chromatic Number of Random Triangle‐Free Graphs
Random Structures & Algorithms · 2026-07 · 68 (4)
DOI: 10.1002/rsa.70081 ↗Kurz gefasst
Fachartikel in der Zeitschrift Random Structures & Algorithms, online erschienen am 06.06.2026. Verfasst von Clayton Mizgerd und 2 weiteren Autor:innen. Die Arbeit nennt 49 Literaturangaben. Gefördert von: National Science Foundation.
Abstract (Originalsprache)
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.
Förderung
- National Science Foundation
Zitieren
APA
Mizgerd, C., Perkins, W., & Wang, Y. (2026). On the Chromatic Number of Random Triangle‐Free Graphs. Random Structures & Algorithms, 68(4). https://doi.org/10.1002/rsa.70081
Vancouver
Mizgerd C, Perkins W, Wang Y. On the Chromatic Number of Random Triangle‐Free Graphs. Random Structures & Algorithms. 2026;68(4). doi:10.1002/rsa.70081
BibTeX
@article{Mizgerd2026,
author = {Mizgerd, Clayton and Perkins, Will and Wang, Yuzhou},
title = {On the Chromatic Number of Random Triangle‐Free Graphs},
journal = {Random Structures & Algorithms},
year = {2026},
volume = {68},
number = {4},
doi = {10.1002/rsa.70081}
}
EUVIMED