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

Cet article est une ébauche concernant la théorie des graphes.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

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ésolu en 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 $k\in \{1,\dots ,12\}$ a été prouvée numériquement en 2012 par David Romero et Federico 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 modifier

↑ (en) David Romero et Federico Alonso-Pecina, « The Erdős–Faber–Lovász conjecture is true for n ≤ 12 », World Scientific Publishing Company,‎ 2014, p. 5 (lire en ligne).
↑ Jeff Kahn et Paul D. Seymour, « A fractional version of the Erdős-Faber-Lovász conjecture », Combinatorica, vol. 12, n^o 2,‎ 1992, p. 155–160 (DOI 10.1007/BF01204719, MR 1179253).

Portail de l'informatique théorique

[1] (en) David Romero et Federico Alonso-Pecina, « The Erdős–Faber–Lovász conjecture is true for n ≤ 12 », World Scientific Publishing Company,‎ 2014, 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, n^o 2,‎ 1992, p. 155–160 (DOI 10.1007/BF01204719, MR 1179253).

[1]

[2]