Skip to content
DraconiticResearch
Search Sources API
185,139 studies31 sourcesUpdated 56 min ago
PreprintCC BY 4.0arXiv

Erdős-Hajnal for excluding paths

  • Tung H. Nguyen
Open at sourcePDFDOICite

Abstract

We prove the Erdős-Hajnal conjecture for excluding an arbitrary path. A major step in our proof is a novel Gyárfás path argument based on the ideas of bookkeeping blockades and splitting paths, which may be of independent interest.

Related

  1. The Erdős--Hajnal property for paths
    Shenwei Huang, Yidong Zhou, Yuwen Zhou
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. The Erdős-Hajnal Property for the six-vertex Graph with Edge Set {ab,bc,cd,de,af,bf,df}
    Viet-Hoang Tran, Tan M. Nguyen
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  3. On the solution to the Erdős-Hajnal problem on high-girth high-chromatic subgraphs
    Tung Nguyen, Bartosz Walczak
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. Equivalence between Erdős–Hajnal and polynomial Rödl and Nikiforov conjectures
    Matija Bucić, Jacob Fox, Huy Tuan Pham
    Bulletin of the London Mathematical SocietyPeer-reviewedCC BYFull text6 citedCombinatorics & discrete mathematicsOpenAlex
  5. The Erdős--Hajnal hypergraph Ramsey problem for r4(6,n)
    Longma Du, Xinyu Hu, Ruilong Liu +1
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{nguyen2026erdőshajnal,
  title = {{Erdős-Hajnal for excluding paths}},
  author = {Tung H. Nguyen},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.24887},
  eprint = {2610.24887},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.24887},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Erdős-Hajnal for excluding paths
AU  - Tung H. Nguyen
PY  - 2026
DA  - 2026/10/20
PB  - arXiv
DO  - 10.48550/arxiv.2610.24887
UR  - https://arxiv.org/abs/2610.24887
AB  - We prove the Erdős-Hajnal conjecture for excluding an arbitrary path. A major step in our proof is a novel Gyárfás path argument based on the ideas of bookkeeping blockades and splitting paths, which may be of independent interest.
ER  -