Erdős-Hajnal conjecture beyond five-vertex graphs
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2606.06258
curl -X POST /api/v1/records/arxiv/2606.06258/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2606.06258/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'