Erdős Problem #108
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: graph theory, chromatic number, cycles.
Read this status correctly
The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.
The question in plain language
The chromatic number \(\chi(G)\) of a graph is the minimum number of vertex colours avoiding monochromatic edges. Its girth is the length of its shortest cycle, with forests assigned infinite girth. Erdős and Hajnal asked whether very large chromatic number forces a subgraph that is both highly chromatic and free of short cycles.
More precisely, for every integer \(r\ge4\) and \(k\ge2\), does a finite threshold \(f(k,r)\) exist such that every graph of chromatic number at least \(f(k,r)\) contains a subgraph \(H\) satisfying
The desired subgraph is not necessarily induced. The quantifier allows \(f(k,r)\) to depend on both parameters but not on the host graph's number of vertices.
A small example
A triangle has chromatic number three and girth three. Removing one edge leaves a bipartite path of girth infinity but chromatic number two. Thus simply deleting a shortest cycle can destroy the desired chromatic complexity.
There are triangle-free finite graphs of arbitrarily large chromatic number, so large chromatic number is not always caused by triangles. The problem asks to extract such high-girth complexity inside an arbitrary graph with sufficiently high chromatic number.
What is known
The general statement remains OPEN. Rödl proved the case \(r=4\) in On the chromatic number of subgraphs of a given graph, Proceedings of the American Mathematical Society 64 (1977), 370–371. Since a simple graph's cycles have length at least three, the constraint girth at least four means triangle-free. This proof does not cover \(r=5\), which also forbids four-cycles.
The maintained catalogue separately asks if the thresholds necessarily grow very rapidly with \(r\), specifically whether
That asymptotic refinement cannot be taken as a consequence of existence, and depends on precise conventions for the minimal threshold.
A related problem about preserving infinite chromatic number while increasing girth is another, stronger question; using an ordinary finite Erdős high-girth/high-chromatic construction is not enough to answer the extraction property.
GCL's current state
The pinned catalogue and maintained #108, edited January 2026, mark it OPEN. Source issue #1377 is preserved. Rödl's precise \(r=4\) published bibliographic information is checked through the historical problem record, but his full proof has not been independently reproduced.
The original issue contains an authenticated RESULT/1 source report. This is unadjudicated source evidence only, not independent mathematical certification or editorial admission.
What remains
A bounded test is to enumerate graphs on up to six vertices, calculate girth and chromatic number exactly, and verify that every reported triangle-free subgraph has girth at least four. Acceptance: every tested subgraph uses only edges of its host, girth is computed from simple cycles, and forests are assigned infinite girth. This is a source-semantics fixture, not a proof of uniform \(f(k,r)\) for unbounded graphs.
Sources and claim boundaries
No new high-girth extraction theorem, primary complete-proof replay or editorial admission is claimed.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1377 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: PROTECTED_READY_BACKLOG.
- Formal-statement coverage: A provider statement was included in the pinned snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.