On the solution to the Erdős-Hajnal problem on high-girth high-chromatic subgraphs

@misc{nguyen2026solution,
  title = {{On the solution to the Erdős-Hajnal problem on high-girth high-chromatic subgraphs}},
  author = {Tung Nguyen and Bartosz Walczak},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2609.40192},
  eprint = {2609.40192},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.40192},
}

TY  - UNPB
TI  - On the solution to the Erdős-Hajnal problem on high-girth high-chromatic subgraphs
AU  - Tung Nguyen
AU  - Bartosz Walczak
PY  - 2026
DA  - 2026/10/01
PB  - arXiv
DO  - 10.48550/arxiv.2609.40192
UR  - https://arxiv.org/abs/2609.40192
AB  - 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$'.
ER  -