← All problems

Erdős Problem #108 — High-girth high-chromatic subgraphs

57 years old · traced to

For integers r≥4r\ge 4 and k≥2k\ge 2, does there exist a finite integer f(k,r)f(k,r) such that every graph GG with chromatic number at least f(k,r)f(k,r) has an ordinary subgraph HH satisfying

girth⁡(H)≥randχ(H)≥k?\operatorname{girth}(H)\ge r \qquad\text{and}\qquad \chi(H)\ge k?

Here χ\chi denotes chromatic number, girth is the length of the shortest cycle (taken to be infinite for an acyclic graph), and “subgraph” allows deletion of vertices and edges; it does not require HH to be induced. Erdős Problem #108 Kohlmeyer–Kruer, A Counterexample to Erdős Problem 108 via Arc Graphs (2026 preprint)

Background

Erdős and Hajnal conjectured that sufficiently large chromatic number forces a subgraph that remains highly chromatic while avoiding all cycles shorter than a prescribed length. This asks for more than the existence of graphs that are themselves both high-chromatic and high-girth: the desired subgraph must be found inside every graph above a chromatic threshold. Rödl proved the case r=4r=4, where the required subgraph is triangle-free. Erdős also posed a related growth question about how rapidly thresholds would have to increase with the girth parameter. Erdős Problem #108

References

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.