Erdős Problem #717
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: proved (not automatically the live result).
Subject areas: graph theory.
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
For a graph G on n vertices with chromatic number χ(G), define σ(G) as the largest k for which G contains a topological K_k (a subdivision of the complete graph). Erdős and Fajtlowicz conjectured χ(G)≤C sqrt(n) σ(G)/log n for a universal C and sufficiently large n. The maintained source marks PROVED by Fox, Lee and Sudakov in 2013. This is not the original stronger Hajós conjecture χ(G)≤σ(G), which is false in general.
A small example
For G=K_4, χ(G)=4 and σ(G)=4. A subdivision of K_k needs at least k branch vertices, so σ(K_4)=4. This one graph satisfies the theorem's qualitative dependence, but the asymptotic factor sqrt(n)/log n and the universal constant cannot be tested from a single small graph.
What is known
PRIMARY AUTHOR abstract directly available: Jacob Fox, Choongbum Lee and Benny Sudakov, 'Chromatic number, clique subdivisions, and the conjectures of Hajós and Erdős–Fajtlowicz', Combinatorica 33 (2013), 181–197, DOI 10.1007/s00493-013-2853-x; author arXiv:1107.1920. It establishes the precise O(sqrt n/log n) bound for χ/σ; earlier Erdős–Fajtlowicz random graph lower bound shows sharpness up to constants. Catlin counterexamples invalidate the stronger Hajós bound, not the weaker proved statement. The exact original 1981 pages and whole published proof not independently read.
GCL's current state
The authenticated original source return remains in its original BOUNDED_TASK_DESIGNED state. This is an editorially reviewed explanatory article in protected EC-BULK-005-R7, subject to that PR's protected merge. Original research theorem proofs and any external formalizations are attributed to their authors, not newly GCL-certified. The historical source and proof-review limitations recorded in the return remain applicable.
What remains
ERDOS-717-CHROMATIC-TOPOLOGICAL-CLIQUE. Inspect the Fox–Lee–Sudakov theorem with n≥2 and constants, and verify the σ(G) topological subdivision convention. Derive the known random-graph lower interface from a source-locked estimate rather than extrapolating K4 fixture.
Sources and claim boundaries
Maintained source #717 · GCL issue report. Full original mathematical arguments not independently replayed; no independent theorem proof certification.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1988 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
- Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.