Théorème de Grötzsch

En mathématiques, et particulièrement en théorie des graphes, le théorème de Grötzsch est un théorème qui affirme qu'un graphe planaire sans triangle peut être coloré avec seulement trois couleurs. Selon le théorème des quatre couleurs, les sommets de tout graphe planaire peuvent être colorés en utilisant au plus quatre couleurs, de sorte que les deux extrémités de chaque arête aient des couleurs différentes ; par le théorème de Grötzsch, trois couleurs suffisent pour les graphes planaires qui ne contiennent pas trois sommets mutuellement adjacents.

Une 3-coloration d'un graphe planaire sans triangle

Historique du théorème

Le théorème porte le nom du mathématicien allemand Herbert Grötzsch, qui en a publié une preuve en 1959[1]. La preuve originale de Grötzsch était complexe. Claude Berge[2] a tenté de simplifier la démonstration, mais sa preuve était incorrecte[3].

En 2003, Carsten Thomassen[4] déduit une autre preuve d'un théorème apparenté, à savoir que tout graphe planaire avec une maille d'au moins cinq est 3-liste colorable. Cependant, le théorème de Grötzsch lui-même ne s'étend pas depuis la coloration usuelle à la coloration par liste : il existe des graphes planaires sans triangle qui ne sont pas colorables par listes de 3 couleurs. En 1989, Richard Steinberg et Dan Younger[5] ont donné la première preuve correcte, en anglais, de la version duale de ce théorème. En 2012, Nabiha Asghar[6] a donné une preuve nouvelle et beaucoup plus simple du théorème qui s'inspire du travail de Thomassen.

Familles plus larges de graphes
Le graphe de Grötzsch est un graphe sans triangle non planaire qui n'est pas 3 coloriable.

Un résultat légèrement plus général est également vrai, à savoir : si un graphe planaire a au plus trois triangles, il est 3-colorable[3]. Toutefois, le graphe complet planaire K4, et une infinité d'autres graphes planaires contenant K4, contiennent quatre triangles et ne sont pas 3-colorables. En 2009, Zdeněk Dvořák, Ken-ichi Kawarabayashi et Robin Thomas ont annoncé une preuve d'une autre généralisation, conjecturée en 1969 par L. Havel : il existe une constante d telle que, si un graphe plan n'a pas deux triangles à une distance au plus d l'un de l'autre, alors il peut être coloré avec trois couleurs[7]. Ce travail a valu à Dvořák, avec d'autres, le prix européen de combinatoire 2015[8].

Le théorème ne peut pas être généralisé à tous les graphes sans triangle non planaires : les graphes sans triangle non planaires ne sont pas tous 3-colorables. En particulier, le graphe de Grötzsch et le graphe de Chvátal sont des graphes sans triangle nécessitant quatre couleurs, et la transformation mycielskienne peut être utilisée pour construire des graphes sans triangle qui nécessitent un nombre arbitrairement élevé de couleurs.

Le théorème ne peut pas non plus être généralisé à tous les graphes planaires sans K4 : Un graphe planaire qui nécessite 4 couleurs ne contient pas nécessairement le graphe K4. En particulier, il existe un graphe planaire sans cycle de longueur 4 qui ne peut pas être coloré avec 3 couleurs[9].

Factorisation par un homomorphisme

Une 3-coloration d'un graphe G peut être décrite par un homomorphisme de graphes de G dans le triangle K 3. Dans le langage des homomorphismes, le théorème de Grötzsch affirme que tout graphe planaire sans triangle admet un homomorphisme dans K 3 . Naserasr a montré que tout graphe planaire sans triangle admet également un homomorphisme dans le graphe de Clebsch qui est un graphe 4-chromatique. En combinant ces deux résultats, on peut montrer que tout graphe planaire sans triangle admet un homomorphisme dans un graphe 3-coloriable sans triangle qui est le produit tensoriel de K 3 et du graphe de Clebsch. La coloration du graphe peut alors être récupérée en composant cet homomorphisme avec l'homomorphisme du produit tensoriel sur son facteur K 3. Cependant, le graphe de Clebsch et son produit tensoriel avec K 3 sont tous deux non planaires ; il n'existe pas de graphe planaire sans triangle auquel tout autre graphe planaire sans triangle peut être envoyé par un homomorphisme[10],[11].

Représentation géométrique

Un résultat de de Castro et al. de 2002[12] combine le théorème de Grötzsch avec la conjecture de Scheinerman sur la représentation des graphes planaires sous forme de graphes d'intersection de segments de droites . Ils ont prouvé que tout graphe planaire sans triangle peut être représenté par une collection de segments de droites, avec trois pentes, de sorte que deux sommets du graphe sont adjacents si et seulement si les segments de droites qui les représentent se croisent. Une coloration en 3 couleurs du graphe peut alors être obtenue en attribuant à deux sommets la même couleur quand leurs segments de droite ont la même pente.

Complexité informatique

Étant donné un graphe planaire sans triangle, une 3-coloration du graphe peut être trouvée en temps linéaire[13].

Notes
  1. Grötzsch 1959.
  2. Berge 1960.
  3. Grünbaum 1963.
  4. Thomassen 2003.
  5. Steinberg et Younger 1989.
  6. Asghar 2012.
  7. Dvořák, Kawarabayashi et Thomas 2009.
  8. Dvořák, Kráľ et Thomas 2009.
  9. Heckman 2007.
  10. Naserasr 2007, Theorem 11
  11. Nešetřil et Ossona de Mendez 2012.
  12. de Castro et al. 2002.
  13. Kowalik 2010.

Références

Bibliographie
  • Portail des mathématiques
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.