The problem
Given \(n\) sets, each of size \(n\), pairwise intersecting in at most one element, the union can be coloured with \(n\) colours so that each set gets all distinct colours. (Resolved 2021.)
The Erdős–Faber–Lovász conjecture
historicHistory & significance
Erdős–Faber–Lovász posed it in 1972 after a party conversation: it asks whether pairwise-grazing cliques can always be coloured with no more colours than their size. Kahn–Seymour (1992) proved it asymptotically (\(n + o(n)\) colours). The exact conjecture stood for nearly fifty years until Kang–Kelly–Kühn–Methuku–Osthus (2021) proved it for all large \(n\) via the absorption method, with a companion fractional-colouring proof. Small values of \(n\) were checked against the asymptotic threshold, completing the resolution.
More in Graph theory
- same area The strong perfect graph theorem
- same area The Petersen colouring conjecture
- same area The total colouring conjecture
References
- primaryRead the primary source →
The resolution (human proof)
Kang–Kelly–Kühn–Methuku–Osthus (2021) proved that \(n\) sets of size \(n\), pairwise intersecting in at most one point, have chromatic number at most \(n\) for all large \(n\), with small cases verified — closing a problem open since 1972.
Verified by curator — see the API for full claim provenance.