Track new results across pure and applied mathematics.
Search papers, labs, and topics across Lattice.
This paper elucidates a construction method for triangle-free graphs with arbitrarily large chromatic number, demonstrating that subgraphs with no four-cycles possess a limited chromatic number. The authors optimize a recent result by Kohlmeyer and Kruer, reducing the bound on the chromatic number of these sparse subgraphs from 6 to 3. This work addresses a long-standing problem posed by Erdős and Hajnal concerning the existence of high-girth, high-chromatic subgraphs.
Arbitrarily large chromatic number graphs can be triangle-free, yet their 4-cycle-free subgraphs have a chromatic number of only 3.
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$'.