Théorème des quatre couleurs

On voit que l'énoncé classique du théorème des quatre couleurs n'est bien sûr pas une caractérisation des graphes dont le nombre chromatique est inférieur ou égal à quatre puisque le graphe ${\displaystyle K_{3,3}}$ n'est pas planaire mais est biparti. D'autre part, pour des raisons de complexité algorithmique, il ne peut exister de caractérisation simple des graphes k-colorables pour k fixé supérieur ou égal à trois. Le théorème des quatre couleurs se généralise aux graphes sans mineur ${\displaystyle K_{5}}$, puisque le nombre chromatique de ces graphes vaut au plus quatre (et c'est une des motivations de la conjecture de Hadwiger). Une généralisation plus forte encore a été donnée récemment par Guenin :

• les graphes sans mineur impair ${\displaystyle K_{5}}$ sont colorables avec seulement quatre couleurs.

(Un mineur est dit impair si les opérations de contractions des arêtes s'effectuent uniquement sur une coupe du graphe. Un graphe contient un mineur impair ${\displaystyle K_{5}}$ s'il contient un ${\displaystyle K_{5}}$ dont on a remplacé les dix arêtes par dix chemins de longueur impaire.)

Ces résultats plus forts sont basés sur des preuves utilisant le théorème des quatre couleurs lui-même, par conséquent ils n'en apportent pas de nouvelle démonstration.

En collant les bords marqués de flèches doubles pour former un cylindre, puis les bords marqués de flèches simples, on obtient un tore avec sept régions se touchant six à six ; ainsi, sept couleurs sont nécessaires

Résultat du collage précédent.

On peut aussi considérer le problème du coloriage de cartes tracées sur des surfaces autres que le plan. Sur la sphère, le problème est le même (pour le voir, il suffit de retirer un point de la sphère intérieur à l'une des régions, et d'effectuer une projection stéréographique).

En 1890, Heawood démontra que pour une surface « fermée » (c'est-à-dire compacte, connexe et sans bord) non homéomorphe à la sphère, le nombre de couleurs nécessaires est toujours majoré, en fonction de la caractéristique d'Euler χ de la surface, par

${\displaystyle p:=\left\lfloor {\frac {7+{\sqrt {49-24\chi }}}{2}}\right\rfloor }$

(où les crochets extérieurs désignent la fonction partie entière) et conjectura que ce majorant était optimal.

(Le théorème des quatre couleurs est l'extension à la sphère de sa majoration, puisqu'alors, χ = 2 donc p = 4.)

Par exemple, le tore a une caractéristique d'Euler χ = 0 donc p = 7 ; 7 couleurs suffisent donc pour colorier n'importe quelle carte sur le tore, et l'exemple de la figure montre que cela peut être nécessaire.

En 1934, Philip Franklin réfuta la conjecture de Heawood en montrant que pour la bouteille de Klein, 6 couleurs suffisent toujours, alors que, comme pour le tore, χ = 0 donc p = 7 (il exhiba de plus une carte pour laquelle 6 couleurs sont nécessaires). Mais en 1968, Ringel et John William Theodore Youngs montrèrent que la conjecture est vraie pour toute autre surface fermée, c'est-à-dire qu'il existe une carte tracée sur cette surface pour laquelle p couleurs sont nécessaires.

Il n'y a pas de généralisation dans l'espace car n boudins assez longs peuvent toujours être disposés de telle façon que chacun touche tous les autres — ce qui rend supérieur à n le nombre de couleurs nécessaires — et n peut être choisi aussi grand qu'on veut.

Coloriage des États des États-Unis en quatre couleurs.

Déterminer si un graphe peut être ou non coloré en deux couleurs est très facile : techniquement, il suffit de colorier arbitrairement un sommet de chaque composante connexe avec une couleur et ensuite de propager cette décision en colorant les sommets voisins avec l'autre couleur, et ainsi de suite. Si l'on rencontre un sommet encore non coloré et voisin de deux sommets de couleur différente, alors le graphe ne peut être biparti. C'est un problème soluble en temps polynomial.

En revanche, déterminer si un graphe peut être ou non coloré en k couleurs pour k > 2 est un problème NP-complet. La preuve de Appel et Haken donne un algorithme pour colorier tout graphe planaire avec quatre couleurs en temps quadratique (la 3-coloration des graphes planaires étant NP-complet).

S'agissant du coloriage des cartes de géographie, le théorème a, en fait, un intérêt limité. Par exemple, si on souhaite colorier une carte géographique du monde en attribuant des couleurs différentes aux pays limitrophes :

• D'une part, on sera gêné par la présence de la mer. Soit il faut lui attribuer une couleur comme si c'était un pays — mais ce serait trompeur — soit il faut lui réserver une couleur supplémentaire.
• D'autre part, le théorème traite de régions connexes, or les pays ne sont pas forcément connexes, car leur territoire peut inclure des îles ou des exclaves.