# Erdős–Faber–Lovász conjecture

**Conjecture**If is a simple graph which is the union of pairwise edge-disjoint complete graphs, each of which has vertices, then the chromatic number of is .

From [Erd81]: "Faber, Lovász and I made this harmless looking conjecture at a party in Boulder Colorado in September 1972. Its diffculty was realised only slowly. I now offer 500 dollars for a proof or disproof. (Not long ago I only offered 50; the increase is not due to inflation but to the fact that I now think the problem is very diffcult. Perhaps I am wrong.)"

The conjecture can be equivalently formulated in terms of seating assignments or hypergraph colouring; see Wikipedia or Doug West's Webpage.

## Bibliography

[Erd81] P. Erdős. On the combinatorial problems which I would most like to see solved. Combinatorica, 1(1):25–42, 1981.

* indicates original appearance(s) of problem.