Paperlane

no. 7 · Tuesday 3 November 2026

The Erdős–Hajnal property for paths

Shenwei Huang, Yidong Zhou and Yuwen Zhou

math.CO · 28 pp

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 $n^{c}$. In this paper, we prove that the Erdős-Hajnal conjecture holds for every path.

comments
28 pages, 1 figure
fields
Combinatorics
pdf ↗ page arXiv:2611.01963 ↗