Science Fair Project Encyclopedia
Erdos-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.
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 √(k − 1).
See also
References
- Erdős, Paul (1981). On the combinatorial problems I would most like to see solved. Combinatorica 1, 25–42.
10-26-2009 08:16:03
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details