Erdős–Faber–Lovász Conjecture

In graph theory, the Erdős–Faber–Lovász conjecture is an unsolved problem about graph coloring, named after Paul Erdős, Vance Faber, and László Lovász, who formulated it in 1972. It says:

If k complete graphs, each having exactly k vertices, have the property that every pair of complete graphs has at most one shared vertex, then the union of the graphs can be colored with k colors.

Read more about Erdős–Faber–Lovász Conjecture:  Equivalent Formulations, History and Partial Results, Related Problems

Other articles related to "conjecture":

Erdős–Faber–Lovász Conjecture - Related Problems
... A version of the conjecture that uses the fractional chromatic number in place of the chromatic number is known to be true ... a finite calculation suffices to verify that the conjecture is true for all simple hypergraphs with that value of L ... Based on this idea, he shows that the conjecture is indeed true for all simple hypergraphs with L ≤ 10 ...

Famous quotes containing the word conjecture:

    What these perplexities of my uncle Toby were,—’tis impossible for you to guess;Mif you could,—I should blush ... as an author; inasmuch as I set no small store by myself upon this very account, that my reader has never yet been able to guess at any thing. And ... if I thought you was able to form the least ... conjecture to yourself, of what was to come in the next page,—I would tear it out of my book.
    Laurence Sterne (1713–1768)