{"id":"arxiv/2606.06258","url":"https://arxiv.org/abs/2606.06258","tags":["math.CO"],"score":0,"title":"Erdős-Hajnal conjecture beyond five-vertex graphs","domain":"math.CO","source":"arxiv","authors":["Shenwei Huang","Yiao Ju","Yidong Zhou"],"reviews":0,"subject":"math.CO","summary":"In 1989, Erdős and Hajnal conjectured 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}$. This conjecture, known as the Erdős-Hajnal conjecture, is a central open problem in combinatorics and listed as one of the top 10 Erdős problems by Bloom on the Erdős problem website https://www.erdosproblems.com/. In a recent breakthrough, Nguyen, Scott and Seymour proved that Erdős-Hajnal conjecture holds for the case when $H$ is the five-vertex path, which, combined…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-06-04","reactions":{}}