Un patron en couleurs, mais pas trop

Une question m'a été posée sur l'article Ton patron est triste ? Peins-le ! : comment peut-on s'y prendre pour colorier le patron du prisme à base triangulaire avec trois couleurs.

Alors voilà, je pense qu'il est pratique de passer par un graphe. Mais je ne vais pas me lancer dans la théorie des graphes et "simplement" répondre la question posée, de mon mieux. Cela étant, la méthode proposée est bourrin et fastidieuse. Il y a sans doute moyen de se l'approprier de façon plus intuitive, mais je crois que passer par le détail permet de prendre du recul plus facilement ensuite.

Commençons par nommer chaque zone. Cela suppose déjà de réfléchir à la façon dont se repliera patron pour former le solide. J'ai obtenu 30 zones (j'espère ne pas m'être trompée...).

Ensuite, on représente chaque zone par la lettre correspondante. Et on va relier les lettres des zones adjacentes. C'est un graphe, que l'on obtient là. Et il est trèèès indigeste.

Hé bien en fait on ne peut pas colorer ce graphe de trois couleurs. En effet, regardons par exemple les zones que j'ai nommées V, W, X et Y. Chacune d'elles est adjacente (c'est-à-dire touche) chacune des trois autres. On appelle cette configuration un sous-graphe (parce que c'est un bout du graphe entier) complet (car chaque sommet de ce sous-graphe est relié aux autres). Or, pour colorer le graphe et colorier le patron, il faut une couleur différente pour deus zones adjacentes. Si on peut trouver un sous-graphe complet à quatre sommets, c'est qu'il faut au moins quatre couleurs différentes. C'est donc fichu pour trois couleurs.

Combien de couleurs faut-il alors au minimum ? (on appelle ça le nombre chromatique du graphe)

On indique le degré de chaque sommet, c'est-à-dire le nombre d'arêtes qui le concernent. La méthode classique consiste ensuite à attribuer une couleur au sommet de plus grand sommet. Ici, G. On va attribuer la même couleurs aux sommets qui ne sont pas reliés à G, en privilégiant ceux dont le degré est "grand". Et ainsi de suite. Par exemple, j'ai coloré G en rouge, puis Y en rouge. Je ne pouvais alors pas colorer B en rouge, car si B et G ne sont pas reliés, B et Y le sont.

Puis on continue, une fois épuisées les possibilités d'attribuer la première couleur, en réitérant avec la deuxième. C'est un algorithme de coloration : on répète le processus.

Evidemment, on est amené à faire des choix. C'est tout le problème de cette méthode : elle est raisonnable, elle s'inscrit dans une logique d'optimisation, mais elle n'est pas sûre. Sauf si on tombe sur le nombre de couleurs qui correspond au plus grand sous-graphe complet.

En ce qui me concerne, j'ai trouvé cinq couleurs à mon premier essai. Une seule zone m'empêche de trouver quatre couleurs, ce qui me semble indiquer un espoir de descendre à quatre. Mais là, tout de suite, je vais me coucher.

En continuant de réfléchir. Et les coups de main sont les bienvenus, cela va de soi.