Conjecture de Heawood

En théorie des graphes, la conjecture de Heawood ou, maintenant qu'elle est démontrée le théorème de Ringel–Youngs donne un minorant pour le nombre de couleurs nécessaires pour colorer une surface de genre donné. Pour les surfaces de genre 0, 1, 2, 3, 4, 5, 6, 7,... qui sont la sphère et le tore à 1, 2, 3, 4, 5, 6, 7... trous, le nombre de couleurs requises est 4, 7, 8, 9, 10, 11, 12, 12, .... (c'est la suite  A000934), le nombre chromatique ou nombre de Heawood. Pour la sphère, de genre 0, le nombre 4 est l'énoncé de théorème des quatre couleurs.

La conjecture a été formulée en 1890 par Percy John Heawood et définitivement démontrée en 1968 par Gerhard Ringel et John William Theodore Youngs. Un cas, la bouteille de Klein, constitue une exception a la formule générale. Une approche totalement différente a permis de résoudre le problème bien plus ancien du nombre de couleurs nécessaires pour le plan ou la sphère, sa solution en 1976 est le théorème des quatre couleurs démontré par Wolfgang Haken et Kenneth Appel. Sur la sphère, la borne inférieure est facile, alors que pour les genres supérieurs, c'est la majoration qui est facile ; elle a été démontrée par Heawood dans son article original qui contient la conjecture.

Évolution de la preuve

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. Ringel, Youngs et d'autres contributeurs ont construit des exemples extrémaux pour les genres g = 1, 2, 3... En effectuant la division euclidienne par douze, g = 12s + k, les genres se groupent en 12 cas selon la valeur du reste : k = 0, 1,..., 11. Les années où certains des douze cas ont été démontrés, en négligeant quelques cas exceptionnels, sont les suivants  :

• 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.

Énoncé

Le graphe de Franklin.

Percy John Heawood a conjecturé en 1890 que, pour un genre $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 :

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

où $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 :

$\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, la 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.

Exemple

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

Le tore a genre $g=1$, donc $\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.

Références

• 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)

Lien externe

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