QUATRE COULEURS PROBLÈME DES

Les réductions de Kempe

Reprenons l'ensemble inévitable de Kempe :

$$U_K=\left\{v_2,v_3,v_4,v_5\right\},$$

v_i, désignant la configuration formée par un sommet de degré i, ses voisins et le circuit qu'ils engendrent.

On montre aisément que v₂ et v₃ sont réductibles : on obtient T' en effaçant l'intérieur du circuit C (dans le cas de C₂, on simplifie aussi l'arête double en effaçant l'une des arêtes formant C₂). Les circuits C₂ et C₃ n'utilisant pas toutes les couleurs disponibles, T est coloriable en même temps que T'.

Pour v₄, la démonstration est un peu plus délicate. Nous obtenons T' en effaçant l'intérieur du circuit C₄ = A B C D). Si C₄ n'utilise que deux ou trois couleurs, on peut colorier V : on dit que ces coloriages du circuit séparateur sont directs (ils s'étendent directement à la partie intérieure de la configuration). Mais, si A, B, C, D portent des couleurs toutes différentes (soit dans l'ordre cyclique : 1, 2, 3, 4), le coloriage n'est plus directement possible.

Kempe résolut cette difficulté en considérant dans T' le sous-graphe constitué des sommets de couleur 1 ou 3 et des arêtes joignant un sommet de couleur 1 à un sommet de couleur 3 : ce sous-graphe sera désigné par G_1,3. On définira de même le sous-graphe G_2,4, correspondant à l'autre paire de couleurs.

Ces sous-graphes ne peuvent avoir un sommet commun (qui devrait alors être de deux couleurs différentes). Si, dans G_1,3, il n'existe pas de chaîne d'arêtes reliant A à C, nous échangerons les couleurs 1 et 3 dans la composante de G_1,3 qui contient C, obtenant un nouveau coloriage correct de T' où C₄ ne comportera plus la couleur 3, laquelle sera disponible pour colorier V. Si G_1,3 contient une chaîne reliant A à C, cette chaîne sépare G_2,4 en deux parties et B ne peut pas être relié à D dans G_2,4. Une modification similaire de la précédente permet donc d'utiliser pour D la couleur 2, libérant la couleur 4 pour colorier V. En résumé, la topologie du plan permet de modifier le coloriage de C₄ de l'une des deux manières suivantes :

$$1 2 3 4\to 1 2 1 4 ou 1 2 3 4\to 1 2 3 2.$$

1 2 3 4 est appelé coloriage indirect de la configuration.

L'argument de Kempe est un algorithme inductif : il est légitime de considérer comme coloriages indirects non seulement ceux qui se ramènent à des coloriages directs, mais aussi ceux qui se ramènent à des coloriages déjà reconnus comme indirects. Si tous les coloriages du circuit séparateur sont directs ou indirects, la configuration est réductible. Mais il peut subsister des coloriages qui résistent à l'argument de Kempe. Si ces coloriages résiduels sont incompatibles avec les conditions géométriques imposées à T' (qui restreignent les possibilités de coloriage du circuit séparateur), on a encore une réduction, d'un type plus général dû à G. D. Birkhoff. Si l'on ne trouve pas de modification (T → T') éliminant tous les coloriages résiduels, la réduction échoue (ce qui n'est pas pour autant une preuve d'irréductibilité !). Dans la plupart des cas, les coloriages possibles sont si nombreux que leur étude nécessite l'emploi de l'ordinateur.