Théorème de Grötzsch

vignette| Une 3-coloration d'un graphe planaire sans triangle 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. Le théorème porte le nom du mathématicien allemand Herbert Grötzsch, qui en a publié une preuve en 1959. La preuve originale de Grötzsch était complexe. Claude Berge a tenté de simplifier la démonstration, mais sa preuve était incorrecte. En 2003, Carsten Thomassen 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 ont donné la première preuve correcte, en anglais, de la version duale de ce théorème. En 2012, Nabiha Asghar a donné une preuve nouvelle et beaucoup plus simple du théorème qui s'inspire du travail de Thomassen. thumb|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. 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.