{"id":"arxiv/2609.40192","url":"https://arxiv.org/abs/2609.40192","tags":["math.CO"],"score":0,"title":"On the solution to the Erdős-Hajnal problem on high-girth high-chromatic subgraphs","domain":"math.CO","source":"arxiv","authors":["Tung Nguyen","Bartosz Walczak"],"reviews":0,"subject":"math.CO","summary":"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$'.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-30","reactions":{}}