The Erdős-Faber-Lovász conjecture asserts that a graph formed from 
complete graphs, each on
vertices, with any two sharing at most one graph
vertex, has chromatic number 
(Erdős 1981, Kang et al. 2023). Each constituent
complete graph requires 
colors, so the assertion is that these local requirements
can be satisfied simultaneously.
Equivalently, every finite linear hypergraph on 
vertices, with distinct hyperedges of size at least 2, admits a coloring of its
hyperedges with at most 
colors such that intersecting hyperedges
receive different colors (Kang et al. 2023).
The conjecture was posed in 1972, and Kang et al. (2023) proved it for every sufficiently large 
. It is problem
19 in the Erdős problems collection (Bloom
2026).
