Skip to content
DraconiticResearch
Search Sources API
197,768 studies31 sourcesUpdated 43 min ago
PreprintCC BY 4.0arXiv

The Erdős--Hajnal property for paths

  • Shenwei Huang
  • Yidong Zhou
  • Yuwen Zhou
Open at sourcePDFDOICite

Abstract

The well-known Erdős-Hajnal conjecture states that for any graph H, there is a constant c=c(H)>0 such that every n-vertex graph G with no induced copies of H contains a clique or an independent set of size at least nc. In this paper, we prove that the Erdős-Hajnal conjecture holds for every path.

Related

  1. Erdős-Hajnal for excluding paths
    Tung H. Nguyen
    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 text14 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{huang2026erdőshajnal,
  title = {{The Erdős--Hajnal property for paths}},
  author = {Shenwei Huang and Yidong Zhou and Yuwen Zhou},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.01963},
  eprint = {2611.01963},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.01963},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - The Erdős--Hajnal property for paths
AU  - Shenwei Huang
AU  - Yidong Zhou
AU  - Yuwen Zhou
PY  - 2026
DA  - 2026/11/01
PB  - arXiv
DO  - 10.48550/arxiv.2611.01963
UR  - https://arxiv.org/abs/2611.01963
AB  - The well-known Erdős-Hajnal conjecture states that for any graph H, there is a constant c=c(H)>0 such that every n-vertex graph G with no induced copies of H contains a clique or an independent set of size at least n^c. In this paper, we prove that the Erdős-Hajnal conjecture holds for every path.
ER  -