In graph theory, the Erdos-Faber-Lovasz conjecture is a problem about graph coloring, named after Paul Erdos, Vance Faber and Laszlo Lovasz, who formulated it in 1972. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/
Facts
StatementIf k complete graphs, each with exactly k vertices, are arranged so that every pair shares at most one vertex, the union of the graphs can be properly colored with k colors. 1 Proposed Year Progress Toward ResolutionProved for all sufficiently large values of k by Dong Yeap Kang, Tom Kelly, Daniela Kuhn, Abhishek Methuku, and Deryk Osthus, resolving the conjecture asymptotically; the small-k case was not separately addressed in the source consulted. 1 Classification
Resolution Status Chronology
Resolved Year Prize Status
Prize Status (category) Connections
In Branch
Source Erdős-Faber-Lovász conjecture (Wikipedia)
Posed By
Sources
1. Erdos-Faber-Lovasz Conjecture (Wikipedia)
Wikimedia FoundationLead section
named after Paul Erdős, Vance Faber, and László Lovász, who formulated it in 1972
Lead section, formal statement
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 properly colored with k colors.
Lead section, first sentence
who formulated it in 1972
Lead section, second paragraph
The conjecture for all sufficiently large values of k was proved by Dong Yeap Kang, Tom Kelly, Daniela Kühn, Abhishek Methuku, and Deryk Osthus.
View the Source Erdős-Faber-Lovász conjecture (Wikipedia)
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.