Erdős–Faber–Lovász conjecture (original) (raw)
In graph theory, the Erdős–Faber–Lovász conjecture is a 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 properly colored with k colors. A proof of the conjecture for all sufficiently large values of k was announced in 2021 by Dong Yeap Kang, Tom Kelly, Daniela Kühn, Abhishek Methuku, and Deryk Osthus.
| Property | Value |
|---|---|
| dbo:abstract | In graph theory, the Erdős–Faber–Lovász conjecture is a 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 properly colored with k colors. A proof of the conjecture for all sufficiently large values of k was announced in 2021 by Dong Yeap Kang, Tom Kelly, Daniela Kühn, Abhishek Methuku, and Deryk Osthus. (en) En théorie des graphes, la conjecture d'Erdös-Faber-Lovász est un problème de coloration de graphes formulé en 1972 et résoluen 2021 . La conjecture affirme qu'un graphe formé de k cliques de taille k, tel que l'intersection de deux de ces cliques ont au plus un sommet en commun, est un graphe dont le nombre chromatique est inférieur ou égal à k. La conjecture pour a été prouvée numériquement en 2012 par David Romero et Frederico Alonso-Pecina. Une version de la conjecture qui utilise le nombre chromatique fractionnaire au lieu du nombre chromatique est connue pour être vraie. En d'autres termes, si un graphe G est l'union de k k-cliques dont l'intersection deux-à-deux est soit vide, soit réduite à un sommet, alors G peut être k coloré. (fr) Гипотеза Эрдёша — Фабера — Ловаса — это проблема о раскраске графов, названная именами Пала Эрдёша, Ванса Фабера и Ласло Ловаса, которые сформулировали её в 1972 году. Гипотеза гласит: Если k полных графов, каждый из которых имеет в точности k вершин, обладают свойством, что любая пара полных графов имеет не более одной общей вершины, то объединение графов может раскрашено в k цветов. В 2021 году был опубликован препринт с доказательством гипотезы для больших k. (ru) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Erdős–Faber–Lovász_conjecture.svg?width=300 |
| dbo:wikiPageExternalLink | https://doi.org/10.1007/978-3-642-60408-9_26 https://doi.org/10.1016/0095-8956(91)90046-M https://gilkalai.wordpress.com/2021/01/14/to-cheer-you-up-in-difficult-times-17-amazing-the-erdos-faber-lovasz-conjecture-for-large-n-was-proved-by-dong-yeap-kang-tom-kelly-daniela-kuhn-abhishek-methuku-and-deryk-osthus/ https://www.jstor.org/stable/2323901 https://www.quantamagazine.org/mathematicians-settle-erdos-coloring-conjecture-20210405/%7Ctitle=Mathematicians |
| dbo:wikiPageID | 691803 (xsd:integer) |
| dbo:wikiPageLength | 13314 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1087229353 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:List_of_conjectures_by_Paul_Erdős dbr:Partial_linear_space dbr:Paul_Erdős dbr:Vance_Faber dbr:Deryk_Osthus dbr:Intersection_number_(graph_theory) dbc:Conjectures dbc:Graph_coloring dbr:Complete_graph dbr:Graph_(discrete_mathematics) dbr:Graph_coloring dbr:László_Lovász dbr:Clone_(algebra) dbr:Line_graph_of_a_hypergraph dbr:American_Mathematical_Monthly dbr:Edge_coloring dbr:Daniela_Kühn dbr:Fractional_coloring dbr:Graph_theory dbr:Quanta_Magazine dbr:Intersection_graph dbr:Hypergraph dbc:Unsolved_problems_in_graph_theory dbc:Paul_Erdős dbr:Hyperedges dbr:File:Erdős–Faber–Lovász_conjecture.svg |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Harvtxt dbt:Math dbt:Mvar dbt:Refbegin dbt:Refend dbt:Reflist dbt:Sqrt |
| dcterms:subject | dbc:Conjectures dbc:Graph_coloring dbc:Unsolved_problems_in_graph_theory dbc:Paul_Erdős |
| gold:hypernym | dbr:Problem |
| rdf:type | yago:WikicatConjectures yago:Abstraction100002137 yago:Cognition100023271 yago:Concept105835747 yago:Content105809192 yago:Hypothesis105888929 yago:Idea105833840 yago:PsychologicalFeature100023100 dbo:Disease yago:Speculation105891783 |
| rdfs:comment | In graph theory, the Erdős–Faber–Lovász conjecture is a 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 properly colored with k colors. A proof of the conjecture for all sufficiently large values of k was announced in 2021 by Dong Yeap Kang, Tom Kelly, Daniela Kühn, Abhishek Methuku, and Deryk Osthus. (en) Гипотеза Эрдёша — Фабера — Ловаса — это проблема о раскраске графов, названная именами Пала Эрдёша, Ванса Фабера и Ласло Ловаса, которые сформулировали её в 1972 году. Гипотеза гласит: Если k полных графов, каждый из которых имеет в точности k вершин, обладают свойством, что любая пара полных графов имеет не более одной общей вершины, то объединение графов может раскрашено в k цветов. В 2021 году был опубликован препринт с доказательством гипотезы для больших k. (ru) En théorie des graphes, la conjecture d'Erdös-Faber-Lovász est un problème de coloration de graphes formulé en 1972 et résoluen 2021 . La conjecture affirme qu'un graphe formé de k cliques de taille k, tel que l'intersection de deux de ces cliques ont au plus un sommet en commun, est un graphe dont le nombre chromatique est inférieur ou égal à k. La conjecture pour a été prouvée numériquement en 2012 par David Romero et Frederico Alonso-Pecina. (fr) |
| rdfs:label | Erdős–Faber–Lovász conjecture (en) Conjecture d'Erdős-Faber-Lovász (fr) Гипотеза Эрдёша — Фабера — Ловаса (ru) |
| owl:sameAs | freebase:Erdős–Faber–Lovász conjecture wikidata:Erdős–Faber–Lovász conjecture dbpedia-fa:Erdős–Faber–Lovász conjecture dbpedia-fr:Erdős–Faber–Lovász conjecture dbpedia-hu:Erdős–Faber–Lovász conjecture dbpedia-ru:Erdős–Faber–Lovász conjecture https://global.dbpedia.org/id/4ji5S |
| prov:wasDerivedFrom | wikipedia-en:Erdős–Faber–Lovász_conjecture?oldid=1087229353&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Erdős–Faber–Lovász_conjecture.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Erdős–Faber–Lovász_conjecture |
| is dbo:knownFor of | dbr:László_Lovász |
| is dbo:wikiPageDisambiguates of | dbr:Lovász |
| is dbo:wikiPageRedirects of | dbr:Erdoes-Faber-Lovasz_conjecture dbr:Erdos–Faber–Lovasz_conjecture dbr:Erdős-Faber-Lovász_conjecture dbr:Erdos-Faber-Lovasz_conjecture dbr:Erdos-Faber-Lovász_conjecture dbr:Erdös-Faber-Lovász_conjecture |
| is dbo:wikiPageWikiLink of | dbr:List_of_conjectures dbr:List_of_conjectures_by_Paul_Erdős dbr:Vance_Faber dbr:Graph_coloring dbr:László_Lovász dbr:Clique_(graph_theory) dbr:Graph_theory dbr:Erdoes-Faber-Lovasz_conjecture dbr:Erdos–Faber–Lovasz_conjecture dbr:Erdős-Faber-Lovász_conjecture dbr:B-coloring dbr:List_of_things_named_after_Paul_Erdős dbr:List_of_unsolved_problems_in_mathematics dbr:Lovász dbr:Erdos-Faber-Lovasz_conjecture dbr:Erdos-Faber-Lovász_conjecture dbr:Erdös-Faber-Lovász_conjecture |
| is foaf:primaryTopic of | wikipedia-en:Erdős–Faber–Lovász_conjecture |
