Erdős Problem #19
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: decidable (not automatically the live result).
Subject areas: graph theory, chromatic number.
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
Suppose a graph is formed from exactly \(n\) copies of the complete graph on \(n\) vertices, with no edge shared by two copies. Such a graph already needs at least \(n\) colours, because it contains a clique containing \(n\) vertices. Erdős Problem #19, the Erdős–Faber–Lovász conjecture, asks whether \(n\) colours always suffice.
Its status is unusual: resolved up to a finite check. A major published theorem proves the answer for every sufficiently large \(n\), but the original assertion for every value of \(n\) is not thereby established for its remaining finite range.
A small example
For \(n=2\), the graph is the union of two different single edges. They may share one endpoint, giving a three-vertex path, or be disjoint. Either arrangement is bipartite, has an edge, and therefore has chromatic number exactly two. For \(n=1\), the single vertex of the one clique requires just one colour.
These cases illustrate the problem; they cannot substitute for the finite cases with small \(n\) not covered by the general theorem.
What is known
Kang, Kelly, Kühn, Methuku and Osthus, A proof of the Erdős–Faber–Lovász conjecture, Annals of Mathematics 198 (2023), 537–618, prove the conjecture for every sufficiently large size. Their central theorem is formulated using linear hypergraphs: hypergraphs in which two edges intersect in at most one vertex. Properly edge-colouring the hypergraph corresponds to vertex-colouring the graph built from its overlapping cliques.
This is a deep asymptotic theorem, not an exhaustive verification of all finite exceptions. The registry consequently labels the full question DECIDABLE, rather than simply PROVED.
GCL's current state
Source audit #1288 checks the exact remaining finite-parameter boundary and proves the \(n=1,2\) illustrations. No corresponding statement is present in the admitted frozen GCL formal-provider snapshot. The published theorem's full proof and an explicit exhaustive small-case cutoff were not replayed.
What remains
Reconcile an effective threshold for large \(n\) with rigorous verification of all excluded small values before changing the status of the original universal statement. Formal proof work may also require a precise incidence duality relating edge-disjoint cliques and linear hypergraphs.
Sources and claim boundaries
- Erdős Problems #19: DECIDABLE status and finite residual.
- Kang–Kelly–Kühn–Methuku–Osthus (2023), primary journal article, DOI 10.4007/annals.2023.198.2.2: eventual theorem.
- GCL source audit #1288: exact-status boundary, not certification of all finite cases.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1288 — 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.