Precoloring 3-extension on outerplanar graphs

Cet article démontre que pour un graphe extérieur planaire connexe possédant au plus deux triangles, toute précoloration de deux ou trois sommets non adjacents peut être étendue à une coloration propre en trois couleurs de l'ensemble du graphe.

L'essentiel

Imaginez que vous êtes un architecte chargé de peindre un grand dessin géométrique complexe, comme un puzzle de formes qui s'emboîtent parfaitement. Ce dessin représente un graphe (un ensemble de points reliés par des lignes). Votre règle d'or est simple : deux points reliés par une ligne ne doivent jamais avoir la même couleur. Vous avez à votre disposition trois couleurs magiques (disons le rouge, le bleu et le jaune).

Le défi principal de ce papier de recherche est le suivant : Peut-on finir de peindre tout le dessin si quelqu'un a déjà colorié quelques points au hasard ? C'est ce qu'on appelle le problème de l'extension de pré-coloration.

Voici une explication simple de ce que les auteurs, Xingchao Deng et ses collègues, ont découvert, en utilisant des images du quotidien.

1. Le décor : Des graphes "extérieurs"

Les auteurs travaillent sur des graphes spéciaux appelés graphes outerplanaires.

• L'analogie : Imaginez un groupe d'amis assis autour d'une grande table ronde (le bord extérieur). Tout le monde peut voir la table. À l'intérieur, il y a des sous-groupes qui discutent, mais personne n'est "coincé" au milieu de la table sans pouvoir voir le bord. C'est un monde ouvert, sans pièges cachés au centre.
• De plus, ces dessins contiennent très peu de "triangles" (des groupes de trois amis qui se connaissent tous mutuellement). Les auteurs se concentrent sur les dessins qui n'ont qu'un ou deux de ces triangles.

2. Le problème des "Amis Diamant"

L'une des découvertes les plus intéressantes concerne une structure qu'ils appellent le "Diamant".

• L'analogie : Imaginez deux triangles qui partagent un côté commun, formant une forme de losange (comme un diamant de jeu de cartes). Dans ce losange, il y a deux pointes opposées (les sommets du haut et du bas).
• La règle du diamant : Si vous voulez colorier ce losange avec seulement trois couleurs, les deux pointes opposées doivent avoir la même couleur ! C'est une contrainte physique du dessin. Si vous essayez de leur donner des couleurs différentes, tout le système s'effondre et vous ne pouvez plus finir le dessin.
• Les auteurs appellent ces points "sommets diamant". Si on vous demande de pré-colorier ces deux points avec des couleurs différentes, c'est impossible. Mais si on vous donne la même couleur, tout devient possible.

3. Les grandes découvertes (Les Théorèmes)

Les chercheurs ont prouvé deux choses principales, comme s'ils avaient trouvé des clés universelles pour débloquer n'importe quel puzzle :

• Cas 1 : Un seul triangle dans le dessin.
  Peu importe où vous placez trois amis (points) qui ne se touchent pas directement, et peu importe les couleurs que vous leur donnez, vous pourrez toujours finir de colorier tout le dessin avec 3 couleurs. C'est comme si le dessin avait assez de "souplesse" pour s'adapter à n'importe quelle demande initiale.

• Cas 2 : Deux triangles dans le dessin.
  C'est un peu plus strict. Si vous ne pré-coloriez que deux amis :

  • Si le dessin ne contient pas de "Diamant", vous pouvez choisir n'importe quelles couleurs pour ces deux amis.
  • Si le dessin contient un "Diamant" et que vos deux amis sont les pointes de ce diamant, alors vous devez absolument leur donner la même couleur. Si vous respectez cette règle, le reste du dessin se coloriera tout seul.

4. La méthode : Le "Changement de Couleurs" (Algorithme)

Comment ont-ils prouvé cela ? Ils ont utilisé une technique intelligente qu'ils appellent un algorithme de réajustement.

• L'analogie : Imaginez que vous essayez de peindre un long couloir de pièces. Vous commencez à une extrémité avec une couleur. En avançant, vous vous rendez compte que la couleur de la dernière pièce ne correspond pas à celle de votre ami au bout du couloir.
• Au lieu de tout recommencer, vous utilisez une "baguette magique" (une application mathématique appelée homomorphisme) pour changer subtilement les couleurs des pièces intermédiaires, comme un domino qui se renverse, jusqu'à ce que les deux extrémités s'accordent parfaitement.
• Ils ont montré que pour ces graphes spéciaux, on peut toujours faire ce "changement de domino" sans jamais créer de conflit.

En résumé

Ce papier répond à une question vieille de plusieurs décennies : "Jusqu'où peut-on forcer la main d'un coloriste sans casser le jeu ?"

La réponse est rassurante : pour ces dessins géométriques simples (outerplanaires) avec très peu de triangles, le monde est très flexible. À quelques exceptions près (comme la règle stricte du "Diamant"), vous pouvez presque toujours commencer par colorier quelques points au hasard et finir le reste du dessin sans problème. C'est une victoire pour la logique et la structure des formes géométriques !

Résumé technique

Voici un résumé technique détaillé de l'article « A note on the precoloring extension of outerplane graphs » (Une note sur l'extension de précoloration des graphes outerplanaires), rédigé en français.

1. Problématique

L'article aborde le problème de l'extension de précoloration (precoloring extension) appliqué aux graphes outerplanaires (ou outerplane). Ce problème consiste à déterminer si une coloration partielle, assignée à un sous-ensemble de sommets d'un graphe, peut être étendue à une coloration propre $k$-colorée de l'ensemble du graphe.

Le contexte théorique repose sur le célèbre Théorème de Grötzsch, qui établit que tout graphe planaire sans triangle est 3-colorable. Des travaux antérieurs (Grünbaum, Aksionov, La et al.) ont généralisé ce résultat aux graphes planaires contenant un nombre limité de triangles (jusqu'à trois). Cependant, la question de l'extension de la précoloration pour des graphes outerplanaires contenant un ou deux triangles, avec des sommets précolorés spécifiques, reste partiellement ouverte.

L'objectif principal de cet article est de répondre aux Problèmes 4.2 et 4.3 soulevés par La et al. [6], en établissant des conditions sous lesquelles la précoloration de sommets indépendants peut être étendue à une 3-coloration complète pour les graphes outerplanaires biconnexes (et par extension, connexes) contenant au plus deux triangles.

2. Méthodologie

Les auteurs utilisent une approche combinant la théorie des graphes structurelle, les homomorphismes de graphes et des algorithmes de réajustement de coloration.

• Structures Clés :

  • Le "Diamond D" : Une structure composée de deux triangles partageant une arête commune. Les auteurs identifient que dans une 3-coloration propre, les deux sommets indépendants de cette structure (appelés "sommets diamant") doivent nécessairement partager la même couleur.
  • Types de Triangles : Distinction entre triangles internes, triangles rayés (partageant une arête avec la frontière extérieure) et triangles marginaux (partageant deux arêtes avec la frontière).
  • Structures "Gâteau" (Cake) et "Hamburger" : Des configurations spécifiques de triangles et de faces (4-faces ou 5-faces) définies pour faciliter l'analyse des cas.

• Outils Théoriques :

  • Homomorphismes : Utilisation de mappings de graphes vers $K_3$ (le graphe complet à 3 sommets). Les auteurs définissent des mappings spécifiques pour les 4-faces et les 5-faces (notés $f_1$ à $f_6$ et $F_1$ à $F_3$) pour garantir la consistance des couleurs.
  • Ajout de Cordes (Chords) : Transformation du graphe original $G$ en un graphe $H$ en ajoutant des cordes pour décomposer les faces de longueur $\ge 6$ en faces de longueur 4 ou 5, sans créer de nouveaux triangles. Cela permet d'appliquer des résultats connus sur les faces courtes.
  • Algorithme de Réajustement (Algorithm 1) : Un algorithme itératif qui parcourt les faces du graphe en utilisant les homomorphismes définis. Si une contrainte de couleur est violée (par exemple, deux sommets précolorés doivent avoir la même couleur mais les mappings initiaux empêchent cela), l'algorithme modifie le mapping de la face précédente pour rétablir la compatibilité.

• Stratégie de Preuve :
  La preuve est structurée par induction et par cas, en divisant le problème selon le nombre de triangles (un ou deux) et la position des sommets précolorés (dans des triangles, dans des faces, ou dans des structures diamant).

3. Contributions et Résultats Principaux

Les auteurs établissent deux théorèmes principaux pour les graphes outerplanaires biconnexes, suivis de corollaires pour les graphes 1-connexes.

Théorème 1.5 (Un seul triangle)

Pour tout graphe outerplanaire biconnex $G$ contenant exactement un triangle, toute précoloration de trois sommets indépendants peut être étendue à une 3-coloration propre de $G$.

• Preuve : Divisée en trois cas selon la distribution des couleurs initiales (trois couleurs différentes, trois mêmes couleurs, ou deux mêmes et une différente). L'ajout de sommets et d'arêtes virtuels permet de réduire le problème à l'application du Théorème 1.4 (sur les faces 5).

Théorème 1.6 (Deux triangles)

Pour un graphe outerplanaire biconnex $G$ contenant exactement deux triangles, toute précoloration de deux sommets indépendants peut être étendue à une 3-coloration propre, sous réserve de l'une des trois conditions suivantes :

1. $G$ ne contient pas de structure "Diamond D" comme sous-graphe.
2. $G$ contient un "Diamond D", mais les deux sommets précolorés non adjacents ne partagent qu'au plus un sommet du diamant.
3. $G$ contient un "Diamond D" et les deux sommets précolorés non adjacents sont précisément les "sommets diamant" ; dans ce cas, ils doivent avoir la même couleur préassignée.

Corollaires 1.7 et 1.8

Ces résultats s'étendent aux graphes outerplanaires 1-connexes (non biconnexes), car tout tel graphe est un sous-graphe d'un graphe biconnex obtenu par ajout d'arêtes, préservant le nombre de triangles.

4. Signification et Impact

• Résolution de problèmes ouverts : L'article résout partiellement les problèmes 4.2 et 4.3 posés par La et al. [6] dans le contexte des graphes outerplanaires, complétant ainsi la recherche sur l'extension de coloration pour les graphes planaires à faible nombre de triangles.
• Caractérisation des contraintes : L'étude met en lumière le rôle critique de la structure "Diamond" dans la 3-colorabilité. Elle montre que la présence de cette structure impose des contraintes strictes (égalité de couleur) sur les sommets impliqués, et que la violation de cette contrainte rend l'extension impossible.
• Méthodologie Algorithmique : La proposition d'un algorithme de réajustement de couleur basé sur les homomorphismes offre une approche constructive et potentiellement efficace (temps linéaire, selon les remarques de l'article) pour vérifier et réaliser ces extensions de coloration.
• Généralisation : Les résultats renforcent la compréhension de la relation entre la structure topologique (outerplanarité, nombre de triangles) et la colorabilité, offrant un cadre plus large que le théorème classique de Grötzsch.

En conclusion, ce travail fournit une caractérisation complète des conditions d'extension de précoloration pour les graphes outerplanaires avec un ou deux triangles, en intégrant des preuves constructives et des algorithmes de vérification basés sur la théorie des homomorphismes.