{"id":"arxiv/2611.01963","url":"https://arxiv.org/abs/2611.01963","tags":["math.CO"],"score":0,"title":"The Erdős--Hajnal property for paths","domain":"math.CO","source":"arxiv","authors":["Shenwei Huang","Yidong Zhou","Yuwen Zhou"],"reviews":0,"subject":"math.CO","summary":"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.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-11-01","reactions":{}}