Math Conjectures

Erdős–Faber–Lovász Conjecture

OPENMajorConjectureProposed 1972 · Standard version

Canonical statement

Let HH be a finite linear hypergraph on nn vertices, meaning that any two distinct hyperedges meet in at most one vertex. Its hyperedges can be colored with at most nn colors so that intersecting hyperedges receive different colors.
View source LaTeX
Let \(H\) be a finite linear hypergraph on \(n\) vertices,
meaning that any two distinct hyperedges meet in at most one vertex.
Its hyperedges can be colored with at most \(n\) colors so that
intersecting hyperedges receive different colors.
GRAPH-023:[ErdosFaberLovasz1972][KangEtAl2023EFL][KirchwegerPeitlSzeider2023EFL]
Graph theoryCombinatorics

Notes

Erdős, Faber, and Lovász conjectured in 1972 that the hyperedges of any linear hypergraph on nn vertices — one in which two distinct hyperedges share at most one vertex — can be colored with nn colors so that intersecting hyperedges receive different colors. An equivalent, often-quoted formulation asks for an nn-coloring of the union of nn copies of KnK_n that pairwise meet in at most one vertex. Erdős publicized the problem repeatedly and counted it among his favorite combinatorial questions [ErdosFaberLovasz1972].

After nearly fifty years, Kang, Kelly, Kühn, Methuku, and Osthus proved the conjecture for every sufficiently large nn [KangEtAl2023EFL]. Their theorem is asymptotic, however, and leaves a finite range of small nn untreated. Kirchweger, Peitl, and Szeider have attacked precisely such uncovered cases with SAT-solving techniques [KirchwegerPeitlSzeider2023EFL], but the remaining range has not yet been eliminated.

The universal statement — nn colors for every nn — is therefore still formally open, and a full resolution requires closing the finite gap left between the asymptotic proof and the computationally verified small cases.

References (3)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.