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

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.

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.

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 Modèle:Mvar est l'union de Modèle:Mvar Modèle:Mvar-cliques dont l'intersection deux-à-deux est soit vide, soit réduite à un sommet, alors Modèle:Mvar peut être Modèle:Mvar coloré.