Skip to content
DraconiticResearch
Search Sources API
203,203 studies31 sourcesUpdated 14 min ago
PreprintarXiv licencearXiv

Odd-ordered Cayley graphs satisfy Erdős--Gyárfás

  • Michael C. Burkhart
Open at sourcePDFDOICite

Abstract

Erdős and Gyárfás conjectured that every graph with minimum degree at least three contains a power-of-two-length cycle. We prove every Cayley graph of odd order satisfies the conjecture. As a corollary, we find that Cayley graphs of finite nilpotent groups satisfy the conjecture as well.

Related

  1. Towards a more structured search for Erdős-Gyárfás counter-examples
    Guillaume Ducoffe, Bogdan Dumitru
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. Erdős-Gyárfás Balanced Five-Colorings
    Hai Xia, Stefan Szeider
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. Minimal Cayley graphs with large chromatic number
    James Davies, Meike Hatzel, Liana Yepremyan
    arXivPreprintarXiv licenceFull textAlgebra & number theoryCombinatorics & discrete mathematicsarXiv
  4. COLORING SEMIMINIMAL CAYLEY GRAPHS
    Ignacio Garc Ía-Marco, Kolja Knauer, Giuliamaria Menara
    HALPreprintCC BY 4.0Full textGeneral mathematicsHAL
  5. On Edge-Primitive $2$-Arc-Transitive (Bi-)Cayley Graphs
    Hao Nan Chen, Jing Jian Li, Ji Cheng Ma +1
    The Electronic Journal of CombinatoricsPeer-reviewedCC BY 4.0Full textCombinatorics & discrete mathematicsCrossref

Cite

BibTeXRIS
BibTeX
@misc{burkhart2026oddordered,
  title = {{Odd-ordered Cayley graphs satisfy Erdős--Gyárfás}},
  author = {Michael C. Burkhart},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.05060},
  eprint = {2611.05060},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.05060},
}
RIS
TY  - UNPB
TI  - Odd-ordered Cayley graphs satisfy Erdős--Gyárfás
AU  - Michael C. Burkhart
PY  - 2026
DA  - 2026/11/03
PB  - arXiv
DO  - 10.48550/arxiv.2611.05060
UR  - https://arxiv.org/abs/2611.05060
AB  - Erdős and Gyárfás conjectured that every graph with minimum degree at least three contains a power-of-two-length cycle. We prove every Cayley graph of odd order satisfies the conjecture. As a corollary, we find that Cayley graphs of finite nilpotent groups satisfy the conjecture as well.
ER  -