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

Towards a more structured search for Erdős-Gyárfás counter-examples

  • Guillaume Ducoffe
  • Bogdan Dumitru
Open at sourcePDFDOICite

Abstract

The Erdős-Gyárfás conjecture posits that every graph with minimum degree at least three contains a cycle of length some power of two. We prove a few simple structural properties for any minimal counter-example to this conjecture. In particular, the fraction of its vertices of degree three must be greater than 2/3, thus improving on the prior bound of 4/7 (Carr, 2026). Furthermore, it is either biconnected or the $1$-clique-sum of two biconnected graphs. By exploiting some of these properties, we were able to verify the conjecture for every graph of order at most $40$, every bipartite graph of order at most $66$, and every cubic graph of order at most $48$.

Related

  1. Odd-ordered Cayley graphs satisfy Erdős--Gyárfás
    Michael C. Burkhart
    arXivPreprintarXiv licenceFull textAlgebra & number theoryCombinatorics & discrete mathematicsarXiv
  2. Erdős-Gyárfás Balanced Five-Colorings
    Hai Xia, Stefan Szeider
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. Local Search for Almost-Spanning Square Grids in Erdős--Rényi Random Graphs
    Dávid Ferenczi, Alexander Grigoriev
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsProbabilityarXiv
  4. Polylogarithmic bound for the Gyárfás-Sumner conjecture
    Martin Bierbaumer, Matija Bucić
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. Those Confounded Examples
    Stephen R. Cole, Ashley I. Naimi, Paul N. Zivich +1
    American journal of epidemiologyPeer-reviewedLicence not statedFull textStatisticsPMC

Cite

BibTeXRIS
BibTeX
@misc{ducoffe2026towards,
  title = {{Towards a more structured search for Erdős-Gyárfás counter-examples}},
  author = {Guillaume Ducoffe and Bogdan Dumitru},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.28594},
  eprint = {2609.28594},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.28594},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Towards a more structured search for Erdős-Gyárfás counter-examples
AU  - Guillaume Ducoffe
AU  - Bogdan Dumitru
PY  - 2026
DA  - 2026/09/23
PB  - arXiv
DO  - 10.48550/arxiv.2609.28594
UR  - https://arxiv.org/abs/2609.28594
AB  - The Erdős-Gyárfás conjecture posits that every graph with minimum degree at least three contains a cycle of length some power of two. We prove a few simple structural properties for any minimal counter-example to this conjecture. In particular, the fraction of its vertices of degree three must be greater than 2/3, thus improving on the prior bound of 4/7 (Carr, 2026). Furthermore, it is either biconnected or the $1$-clique-sum of two biconnected graphs. By exploiting some of these properties, we were able to verify the conjecture for every graph of order at most $40$, every bipartite graph of order at most $66$, and every cubic graph of order at most $48$.
ER  -