EUVIMEDEUVIMED entdecken
Crossref

On the Chromatic Number of Random Triangle‐Free Graphs

Clayton Mizgerd, Will Perkins, Yuzhou Wang

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →