Skip to content
DraconiticResearch
Search Sources API
203,203 studies31 sourcesUpdated 42 min ago
PreprintCC BY 4.0arXiv

When are random regular triangle-free graphs bipartite?

  • Gregory DeCamillis
  • Pu Gao
Open at sourcePDFDOICite

Abstract

We study the structure of random d-regular triangle-free graphs and show that a sharp phase transition occurs at d=√3/2√(n log n). For smaller d, asymptotically almost surely the graph is non-bipartite, whereas for greater d, asymptotically almost surely the graph is bipartite.

Related

  1. Turán numbers for suspensions of bipartite 2-regular graphs
    Haoxing Wu, Junxue Zhang
    arXivPreprintCC BY-NC-SA 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. Exact three-component covers in 2-coloured random bipartite graphs
    Xiao-Chuan Liu, Xu Yang
    arXivPreprintCC0Full textCombinatorics & discrete mathematicsarXiv
  3. Perfect Partitions of Regular Bipartite Graphs
    Melanie J. Ferreri, Archana L. Parameswaran, Gexin Yu
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. Variance of random greedy independent sets in triangle-free graphs
    Mubin Shaikh
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsProbabilityarXiv
  5. FirstFit coloring process of random bipartite graphs and an online coloring lower bound in the random order model
    Yaqiao Li, Xin Li
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsProbabilityarXiv

Cite

BibTeXRIS
BibTeX
@misc{decamillis2026when,
  title = {{When are random regular triangle-free graphs bipartite?}},
  author = {Gregory DeCamillis and Pu Gao},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2609.17958},
  eprint = {2609.17958},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.17958},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - When are random regular triangle-free graphs bipartite?
AU  - Gregory DeCamillis
AU  - Pu Gao
PY  - 2026
DA  - 2026/10/05
PB  - arXiv
DO  - 10.48550/arxiv.2609.17958
UR  - https://arxiv.org/abs/2609.17958
AB  - We study the structure of random d-regular triangle-free graphs and show that a sharp phase transition occurs at d=√3/2√(n log n). For smaller d, asymptotically almost surely the graph is non-bipartite, whereas for greater d, asymptotically almost surely the graph is bipartite.
ER  -