Accueil🇫🇷Chercher

Conjecture d'Erdős-Faber-Lovász

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.

Un exemple illustrant la conjecture d'Erdős–Faber–Lovász : un graphe composé de quatre cliques de quatre sommets dont deux quelconques ont un sommet en comun, est coloriable en quatre couleurs.

La conjecture pour a été prouvée numériquement en 2012 par David Romero et Frederico Alonso-Pecina[1].

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é[2].

Notes et références

  1. (en) David Romero & Federico Alonso-Pecina, « The Erdős–Faber–Lovász conjecture is true for n ≤ 12 », World Scientific Publishing Company, , p. 5 (lire en ligne).
  2. Jeff Kahn et Paul D. Seymour, « A fractional version of the Erdős-Faber-Lovász conjecture », Combinatorica, vol. 12, no 2, , p. 155–160 (DOI 10.1007/BF01204719, MR 1179253).
Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.