Problem dossier · Graph Theory
Erdős–Faber–Lovász conjecture
If n cliques, each on n vertices, pairwise share at most one vertex, their union can be properly colored with n colors.
§1
Status
Proved for all sufficiently large n (Kang–Kelly–Kühn–Methuku–Osthus, 2021). Small-n cases remain to be closed uniformly.
Think you can crack this one? Read the playbook before you announce →
§2
The Angle of Attack
Generate small-n clique systems and test n-colorability exhaustively; look for extremal configurations that stress the bound; verify the large-n proof's threshold experimentally.
Tags: coloring · cliques · hypergraphs · chromatic number
§3
The Lab
No instruments built yet. When this problem gets tackled, its interactive instruments — explorers, searches, verifiers running in the browser — live here. See the Collatz dossier for what a fully tackled problem looks like.
§4
The Log
Empty. Work on this problem gets logged here as dated entries — constructions tried, code run, dead ends included. Dead ends are results.
§5
Related Problems
More open problems in Graph Theory and adjacent territory.
- Goemans' unsplittable-flow cost conjecture — Graph Theory
- Graffiti conjecture 284 — Graph Theory
- Caccetta–Häggkvist conjecture — Graph Theory
- Frankl's union-closed sets conjecture — Graph Theory
- Lonely runner conjecture — Graph Theory
- No-three-in-line problem — Graph Theory