QUATRE COULEURS PROBLÈME DES

Le principe de déchargement

Nous ne pourrons qu'esquisser dans son principe la description de la stratégie qui permet de constituer un ensemble inévitable de configurations. Nous savons déjà que v₂, v₃ et v₄ sont réductibles. Reprenons l'égalité (1), dont le second membre est strictement positif. On peut considérer que chaque sommet de degré i apporte au premier membre une contribution égale à 6 — i, positive pour i = 5, nulle pour i = 6, négative pour les sommets de degré ≥ 7, qu'on appellera sommets majeurs. On définit un « processus de déchargement » qui, sans changer la somme totale des charges 6 — i, répartit la charge positive de chaque sommet de degré 5 sur les sommets majeurs qui en sont à la distance 1 ou 2 (mesurée en arêtes du graphe). Ce processus complexe, comportant de nombreux cas particuliers, aboutit à l'alternative suivante :

1^o Les charges négatives suffisent à compenser les charges positives : on dit alors que le graphe est totalement déchargé. La somme totale des charges est ≤ 0, ce qui contredit (1).

2^o Il reste des charges positives non compensées, mais les sommets qui les portent font partie de configurations appartenant à un ensemble U. D'après le 1^o, U est un ensemble inévitable. Il suffit donc de réduire toutes les configurations appartenant à U pour obtenir un ensemble inévitable de configurations réductibles et démontrer le théorème.

Réductibilité d'un quadrilatère

Réductibilité du quadrilatère (A. B. Kempe): dans un coloriage des régions, réduction d'une région ayant quatre voisines. C'est la réduction de la figure 1 présentée sous forme duale. Ici, on a colorié la carte, c'est-à-dire les régions et non les sommets. Dans le coloriage du bas,... 

Crédits : Encyclopædia Universalis France

Afficher

L'ordinateur a été utilisé dans les deux phases du problème : construction de l'ensemble U, réduction des configurations appartenant à U. S'il a pu être éliminé après coup de la première phase (processus de déchargement), il n'en est pas de même des nombreuses réductions : un circuit C₁₄, par exemple, possède 199 291 coloriages non équivalents avec quatre couleurs, et chacun doit être étudié. Une démonstration du théorème sans intervention du calcul électronique, si elle est possible, exigera probablement des outils logiques d'une nature toute différente et jettera peut-être une lumière nouvelle sur la difficile conjecture de Hadwiger qui est directement liée au problème des quatre couleurs.

Définition. On appelle contraction d'un graphe G la modification consistant à remplacer deux sommets A, B, joints par une arête, par un sommet C qu'on relie à tous les sommets originairement voisins de A et/ou de B.

Conjecture. Par une suite de contractions, un graphe G dont le coloriage exige n couleurs peut être transformé en K_n le graphe complet de n couleurs.

Cette conjecture, démontrée par G. A. Dirac pour n ≤ 4, est équivalente pour n = 5 au théorème des quatre couleurs (K. Wagner). Pour n > 5, le problème reste ouvert.

1  2  3  4  5 …
pour nos abonnés,
l’article se compose de 4 pages

Médias de l’article

Réduction d'une configuration v4 d'un graphe planaire triangulé
Crédits : Encyclopædia Universalis France

dessin

Réductibilité d'un quadrilatère
Crédits : Encyclopædia Universalis France

dessin

Afficher les 2 médias de l'article