On the solution to the Erdős-Hajnal problem on high-girth high-chromatic subgraphs
A well-known problem of Erdős and Hajnal from the 1960s asks whether every graph with huge chromatic number contains a subgraph with large girth and large chromatic number. Very recently, Kohlmeyer and Kruer provided a strong negative solution to this problem: a construction of triangle-free graphs with arbitrarily large chromatic number whose subgraphs with no four-cycle have chromatic number at most $6$. The purpose of this exposition is to explain the construction method, relate it to relevant literature, and optimise the bound '$6$' to '$3$'.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.40192
curl -X POST /api/v1/records/arxiv/2609.40192/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.40192/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'