Conjecture de Heawood

Dans son article de 1890, Heawood pensait avoir démontré la conjecture, mais peu de temps après la parution de l’article, une erreur a été trouvé dans sa démonstration[2]. Ringel, Youngs et les autres contributeurs ont construit des exemples extrémaux pour les genres g = 1,2,3,.... En posant g = 12s + k, les genres se groupent en 12 cas selon que k = 0,1,2,3,4,5,6,7,8,9,10,11. Les années où les douze cas ont été démontrés, en négligeant quelques cas exceptionnels, sont les suivants[2] :

• 1954, Ringel: cas k=5
• 1961, Ringel: cas k=3,7,10
• 1963, Terry, Welch, Youngs: cas k=0,4
• 1964, Gustin, Youngs: cas k=1
• 1965, Gustin: cas k=9
• 1966, Youngs: cas k=6
• 1967, Ringel, Youngs: cas k=2,8,11

Les cas exceptionnels, au nombre de 7, ont été résolus comme suit :

• 1967, Mayer: cas g=18, 20, 23
• 1968, Ringel, Youngs: cas g=30, 35, 47, 59.

Le traitement de ces derniers cas achève la preuve de la conjecture.

Le graphe de Franklin.

Percy John Heawood a conjecturé en 1890 que, pour un genre ${\displaystyle g>0}$ donné, le nombre minimum de couleurs nécessaires pour colorer tout graphe dessiné sur une surface orientable de ce genre (ou, ce qui est équivalent, pour colorer les régions de toute partition de la surface en régions simplement connexes) est donnée par la formule :

${\displaystyle \gamma (g)=\left\lfloor {\frac {7+{\sqrt {1+48g}}}{2}}\right\rfloor ,}$

où ${\displaystyle x\mapsto \lfloor x\rfloor }$ est la fonction partie entière. Si l'on remplace le genre par la caractéristique d'Euler, on obtient une formule qui couvre à la fois le cas orientable et non orientable, et qui est :

${\displaystyle \gamma (\chi )=\left\lfloor {\frac {7+{\sqrt {49-24\chi }}}{2}}\right\rfloor .}$

Ringel et Youngs ont démontré que cette formule est exacte pour toutes les surfaces à l'exception de la bouteille de Klein. Philip Franklin a démontré en 1930 que la bouteille de Klein requiert au plus 6 couleurs au lieu des 7 couleurs prédites par la formule. Le graphe de Franklin peut être tracé sur la bouteille de Klein de manière à former six régions mutuellement adjacentes, ce qui montre que la borne est atteinte.

La majoration, démontrée dans l'article original de Heawood, est basée sur un algorithme de coloriage glouton. En manipulant la caractéristique d'Euler, on peut montrer que tout graphe plongé dans une surface donnée possède au moins un sommet de degré strictement plus petit que la borne annoncée. Si on supprime ce sommet et on colorie le reste du graphe, le valeur du degré du sommet supprimé assure que le sommet peut être réinséré dans le graphe sans dépasser le nombre de couleurs permises par la borne.

Dans l’autre sens, la démonstration est plus difficile et demande de prouver que dans chaque cas (à l'exception de la bouteille de Klein) un graphe complet avec un nombre de sommets égal au nombre de couleurs données peut être plongé dans la surface.

Une partition du tore en sept régions mutuellement adjacentes, nécessitant sept couleurs.

Le tore a genre ${\displaystyle g=1}$, donc ${\displaystyle \chi =0}$. La formule affirme que toute subdivision du tore en régions peut être coloriée avec sept couleurs. La figure montre une subdivision du tore où chacune des sept régions est adjacente à toutes les autres ; cette subdivision montre que la borne de sept pour le nombre de couleurs est bien atteinte. Le contour de cette subdivision forme un plongement du graphe de Heawood sur le tore.

• Philip Franklin, « A six color problem », MIT Journal of Mathematics and Physics, vol. 13,‎ 1934, p. 363–379 (hdl 2027/mdp.39015019892200)
• Percy John Heawood, « Map colour theorem », Quarterly Journal of Mathematics, vol. 24,‎ 1890, p. 332–338
• Gerhard Ringel et J. W. T. Youngs, « Solution of the Heawood map-coloring problem », Proceedings of the National Academy of Sciences, vol. 60, n^o 2,‎ 1968, p. 438–445 (PMID 16591648, PMCID 225066, DOI 10.1073/pnas.60.2.438, MR 0228378, lire en ligne)

• (en) Eric W. Weisstein, « Heawood Conjecture », sur MathWorld