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 ... He shows that, for any fixed value of L, 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)

Related Phrases

Related Words