| 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
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 13314 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| 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
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:knownFor
of | |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
