Search

The Online Encyclopedia and Dictionary

 
     
 

Encyclopedia

Dictionary

Quotes

 

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.
Last updated: 06-04-2005 08:50:54
Last updated: 10-29-2005 02:13:46