Erdős–Faber–Lovász conjecture

In graph theory, the Erdős–Faber–Lovász conjecture (1972) is a very deep problem about the coloring of graphs. It says:

The union of k copies of k-cliques intersecting in at most one vertex pairwise is k-chromatic.

Paul Erdős originally offered US$50 for proving the conjecture in the affirmative, and later raised the reward to US$500. It is easy to show that the desired chromatic number is less than $1+k{\sqrt {k-1}}$, and it was shown by Kahn that the chromatic number is at most $k+o(k)$.

See also

• Erdős conjecture

References

• Erdős, Paul (1981). On the combinatorial problems I would most like to see solved. Combinatorica 1, 25–42.
• Kahn, Jeff (1992). Coloring Nearly-Disjoint Hypergraphs with $n+o(n)$ Colors. Journal of Combinatorial Theory, Series A 59, 31–39.