Coloration de liste

En théorie des graphes, la coloration de liste est une coloration des sommets d'un graphe où la couleur de chaque sommet est restreinte à une liste de couleurs autorisées. Elle a été étudiée pour la première fois dans les années 1970 dans des articles indépendants par Vadim G. Vizing^[1] et par Paul Erdős, Arthur Rubin (en) et Herbert Taylor^{[2], [3]}.

Étant donné un graphe G et un ensemble ${\displaystyle L(s)}$ de couleurs pour chaque sommet s (appelé sa liste), une coloration de liste est une fonction qui assigne à chaque sommet s à une couleur de la liste ${\displaystyle L(s)}$. Comme pour la coloration usuelle des graphes, une coloration de liste est généralement supposée propre, ce qui signifie que deux sommets adjacents n'ont pas la même couleur. Un graphe est k-choisissable^[4] (ou k-coloriable par liste) s'il admet une coloration de liste propre, quelle que soit la manière dont on attribue des listes de k couleurs à chaque sommet. La choisissabilité (ou coloriabilité de liste ou l'indice chromatique de liste ) ch( G ) d'un graphe G est le plus petit nombre k tel que G soit k-choisissable.

Plus généralement, pour une fonction ${\displaystyle f}$ affectant un entier positif ${\displaystyle f(s)}$ à chaque sommet ${\displaystyle s}$, un graphe G est ${\displaystyle f}$-choisissable (ou ${\displaystyle f}$-coloriable par liste ) s'il a une coloration de liste quelle que soit l'affectation d'une liste de ${\displaystyle f(s)}$ couleurs à chaque sommet ${\displaystyle s}$. En particulier, si ${\displaystyle f(s)=k}$ pour tous les sommets ${\displaystyle s}$, alors la ${\displaystyle f}$-choisissabilité correspond à la k-choisissabilité.

On considère le graphe bipartite complet ${\displaystyle G=K_{2,4}}$ à six sommets A, B, W, X, Y, Z dont la partition est composée de A et B et de W, X, Y et Z d'autre part ; les sommets A et B sont connectés à tous les sommets W, X, Y et Z, et il n'y a pas d'autres arêtes. En tant que graphe biparti, l'indice chromatique habituel de G est 2 : on peut colorer A et B d'une même couleur et W, X, Y, Z d'une même autre couleurs ; ainsi deux sommets adjacents n'ont pas la même couleur. D'autre part, G a un indice chromatique de liste supérieur à 2, comme le montre la construction suivante : on attribue à A et B les listes {rouge, bleu} et {vert, noir} et on attribue aux quatre autres sommets les listes {rouge, vert}, {rouge, noir}, {bleu, vert} et {bleu, noir}. Quel que soit le choix de couleur fait dans la liste de A et dans la liste de B, l'un des 4 autres sommets n'a parmi ses deux choix possibles que des couleurs déjà utilisées pour colorer ses voisins. Ainsi, G n'est pas 2-choisissable.

En revanche, il est facile de voir que G est 3-choisissable : on choisit des couleurs arbitraires pour les sommets A et B ; il reste au moins une couleur disponible pour chacun des autres sommets, et ces couleurs peuvent être choisies arbitrairement.

Plus généralement, soit q un entier positif, et soit G le graphe biparti complet ${\displaystyle K_{q,q^{q}}}$. On suppose qu'il y a ${\displaystyle q^{2}}$ couleurs disponibles que l'on représente par les ${\displaystyle q^{2}}$ nombres distincts à deux chiffres en base q. Pour la composantes à q sommets de la bipartition, on donne aux q sommets les ensembles de couleurs ${\displaystyle \{i0,i1,i2,\ldots \}}$ où les premiers chiffres sont tous égaux, pour les q choix possibles du premier chiffre ${\displaystyle i}$. Pour l'autre composante de la bipartition, on donne aux ${\displaystyle q^{q}}$ sommets des ensembles de couleurs ${\displaystyle \{0a,1b,2c\ldots \}}$ dans lesquels les premiers chiffres sont tous distincts, pour chacun des ${\displaystyle q^{q}}$ choix possibles du q -uplet ${\displaystyle \{0a,1b,2c\ldots \}}$, où ${\displaystyle a,b,c\ldots }$ parcourent toutes les valeurs possibles. La figure du haut de la page montre un exemple de la construction pour ${\displaystyle q=3}$.

Avec cette construction, le graphe G n'a pas de coloration de liste pour ces couleurs : quel que soit l'ensemble de couleurs choisi pour les q sommets du petit côté de la bipartition, ce choix est en conflit avec toutes les couleurs pour l'un des sommets de l'autre côté de la bipartition. Par exemple, si pour q =2, le sommet avec le jeu de couleurs {00,01} est de coloré en 01, et le sommet avec le jeu de couleurs {10,11} est coloré en 10, alors le sommet avec le jeu de couleurs {01,10} ne peut pas être coloré. Par conséquent, l'indice chromatique de liste de G est au moins ${\displaystyle q+1}$^[5].

De même, si ${\displaystyle n={\binom {2k-1}{k}}}$, alors le graphe biparti complet ${\displaystyle K_{n,n}}$ n'est pas k-choisissable. Supposons en effet que ${\displaystyle 2k-1}$ couleurs sont disponibles au total, et que, sur l'un des côtés de la bipartition, chaque sommet a à sa disposition un k-tuple de ces couleurs, différent de chaque autre sommet. Alors, chaque côté de la bipartition doit utiliser au moins k couleurs, car chaque ensemble de ${\displaystyle k-1}$ couleurs est disjoint de la liste d'un sommet. Comme au moins k couleurs sont utilisées d'un côté et au moins k de l'autre, il doit y avoir une couleur qui est utilisée des deux côtés, mais cela implique que deux sommets adjacents ont la même couleur. En particulier, le graphe de l'énigme des trois maisons ${\displaystyle K_{3,3}}$ a un indice chromatique de liste d'au moins trois, et le graphe ${\displaystyle K_{10,10}}$ a un indice chromatique de liste d'au moins quatre^[2].

Pour un graphe G, notons ${\displaystyle \chi (G)}$ l'indice chromatique et ${\displaystyle \Delta (G)}$ le degré maximum de G . L'indice chromatique de liste ch${\displaystyle (G)}$ a les propriétés suivantes :

• ch${\displaystyle (G)\geq \chi (G)}$. Un graphe k-coloriable en liste doit notamment avoir une coloration de liste lorsque chaque sommet se voit attribuer la même liste de k couleurs, ce qui correspond à une coloration en k couleurs habituelle.
• ch${\displaystyle (G)}$ ne peut en général pas être borné en fonction de l'indice chromatique , c'est-à-dire qu'il n'y a pas de fonction ${\displaystyle f}$ telle que ch${\displaystyle (G)\leq f(\chi (G)}$ soit vérifiée pour tout graphe G . En particulier, comme le montrent les exemples de graphes bipartis complets, il existe des graphes avec ${\displaystyle \chi (G)=2}$ mais avec ch${\displaystyle (G)}$ arbitrairement grand.
• ch${\displaystyle (G)\leq \chi (G)\log \,n}$ où n est le nombre de sommets de G.
• ch${\displaystyle (G)\leq 5}$ si G est un graphe planaire^[2],[1],[6].
• ch${\displaystyle (G)\leq 3}$ si G est un graphe biparti planaire^[7].

Les problèmes algorithmiques suivant ont été considérés :

• ${\displaystyle k}$-choisissabilité : décider si un graphe donné est k-choisissable pour un k donné, et
• ${\displaystyle (a,b)}$-choisissabilité : décider si un graphe donné est f -choisissable pour une fonction donnée ${\displaystyle f:V\to \{a,\dots ,b\}}$ .

On sait que la k-choisissabilité dans les graphes bipartis est ${\displaystyle \Pi _{2}^{p}}$ -complet pour tout ${\displaystyle k\geq 3}$, et il en est de même pour la 4-choisissabilité dans les graphes planaires, la 3-choisissabilité dans les graphes planaires sans triangle et la (2, 3)-choisissabilité dans graphes planaires bipartis^[8],[9]. Pour les graphes sans P ₅, c'est-à-dire les graphes excluant les chemins à 5 sommets, la k -choisissabilité est traitable à paramètre fixe^[10].

Il est possible de tester si un graphe est 2-choisissable en temps linéaire en supprimant successivement des sommets de degré zéro ou un jusqu'à atteindre le 2-noyau du graphe, après quoi de telles suppressions ne sont possibles. Le graphe initial est 2-choisissable si et seulement si son 2-noyau est soit un cycle pair, soit un graphe thêta qui est formé de trois chemins avec des extrémités partagées, où deux chemins sontde longueur deux et le troisième chemin de longueur paire^[2].

La coloration de liste se pose dans des problèmes pratiques concernant l'attribution de canal/fréquence^{[11],[12],[13]}

• Aigner, Martin et Ziegler, Günter, Proofs from THE BOOK, Berlin, New York, Springer-Verlag, 2009 (ISBN 978-3-642-00855-9),   Chapter 34 Five-coloring plane graphs.
• Reinhard Diestel, Graph Theory, Springer-Verlag, Heidelberg, coll. « Graduate Texts in Mathematics » (n^o 173), 2016, 447 p. (ISBN 978-3-662-53621-6 et 978-3-96134-005-7, lire en ligne).

• choisissabilité sur wiktionnaire
• Coloration de liste des arêtes

• Portail des mathématiques
• Portail de l'informatique théorique