pipette
ENEnglish

On the solution to the Erd\H{o}s-Hajnal problem on high-girth high-chromatic subgraphs

Tung Nguyen, Bartosz Walczak

Preprint

En palabras de los autores

A well-known problem of Erd\H{o}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 . The purpose of this exposition is to explain the construction method, relate it to relevant literature, and optimise the bound `' to `'.

Resultado principalEl resumen no menciona limitaciones.

Apareció: jueves, 1 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: 14 pages; expository note