Erdős Problem #108 — High-girth high-chromatic subgraphs
For integers and , does there exist a finite integer such that every graph with chromatic number at least has an ordinary subgraph satisfying
Here 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 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 , 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
UnsolvedMath, Erdős Problems set, ULAM AI, licensed CC BY 4.0.
Progress summary
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.