Coloration du graphique (Graph coloring)

Dans la théorie des graphes, la coloration de graphiques implique l'attribution systématique d'étiquettes, classiquement appelées « couleurs », aux éléments d'un graphique. Cette affectation est régie par des contraintes spécifiques, interdisant généralement aux éléments adjacents de partager la même couleur. Ce concept représente une instance spécialisée d’étiquetage de graphiques. L'application la plus fondamentale consiste à attribuer des couleurs aux sommets d'un graphe de telle sorte qu'aucun sommet adjacent ne possède des couleurs identiques ; cette technique spécifique est connue sous le nom de coloration des sommets. De manière correspondante, une coloration des bords implique l'attribution d'une couleur à chaque bord, garantissant qu'aucun bord incident ne partage la même couleur. De plus, pour les graphes planaires, une coloration des faces implique l'attribution d'une couleur à chaque face (ou région) de telle sorte qu'aucune face partageant une limite commune ne se voit attribuer la même couleur.

La coloration des sommets sert fréquemment de concept d'introduction aux problèmes de coloration des graphes, étant donné que divers autres défis de coloration peuvent être reformulés comme des instances de coloration des sommets. Par exemple, une coloration des bords d'un graphe équivaut à une coloration des sommets de son graphe linéaire, et une coloration des faces d'un graphe plan correspond à une coloration des sommets de son graphe double. Néanmoins, les problèmes n’impliquant pas directement la coloration des sommets sont souvent présentés et analysés sous leurs formes originales. Cette approche est en partie due à des considérations pédagogiques et en partie au fait que certains problèmes, tels que la coloration des bords, sont étudiés plus efficacement dans leurs formulations sans sommet.

La pratique consistant à employer des « couleurs » dans ce contexte découle de la tâche historique consistant à colorier les pays sur des cartes politiques, où chaque région était physiquement colorée. Ce concept a ensuite été étendu à la coloration de visages au sein d'un graphe intégré dans un plan. Grâce au principe de dualité planaire, cela a évolué vers la coloration des sommets, une forme qui se généralise à tous les types de graphiques. Dans les cadres mathématiques et informatiques, il est d'usage de représenter ces « couleurs » en utilisant la séquence initiale d'entiers positifs ou non négatifs. Plus largement, n'importe quel ensemble fini peut servir d'« ensemble de couleurs » désigné. Les caractéristiques fondamentales d'un problème de coloration sont déterminées par la quantité de couleurs disponibles, plutôt que par leurs identités spécifiques.

La coloration de graphiques présente de nombreuses applications pratiques ainsi que des défis théoriques importants. Au-delà des types de problèmes classiques, diverses contraintes peuvent être imposées sur la structure du graphe, la méthodologie d'affectation, ou encore les propriétés des couleurs elles-mêmes. Les principes sous-jacents ont même gagné une reconnaissance publique grâce au populaire puzzle numérique, le Sudoku. Par conséquent, la coloration des graphiques reste un domaine de recherche en cours très dynamique.

Contexte historique

Historique

Les premières recherches sur la coloration des graphiques se sont principalement concentrées sur les graphes planaires, en particulier dans le contexte de la coloration des cartes. En 1852, alors qu'il tentait de colorier une carte des comtés anglais, Francis Guthrie proposa la conjecture des quatre couleurs, observant que quatre couleurs semblaient adéquates pour colorer n'importe quelle carte, de sorte qu'aucune région adjacente ne partageait une couleur identique. Frederick Guthrie, le frère de Francis, a ensuite fait part de ce problème à son professeur de mathématiques, Augustus De Morgan de l'University College, qui l'a ensuite évoqué dans une correspondance avec William Hamilton au cours de la même année. Arthur Cayley a officiellement présenté le problème lors d'une réunion de la London Mathematical Society en 1879. La même année, Alfred Kempe a publié un article proposant une solution, ce qui a conduit à considérer le problème des quatre couleurs comme résolu pendant environ une décennie. En reconnaissance de cette réussite, Kempe a été élu membre de la Royal Society et a ensuite été président de la London Mathematical Society.

En 1890, Percy John Heawood démontra la faille de l'argumentation de Kempe. Néanmoins, dans la même publication, Heawood a prouvé le théorème des cinq couleurs, établissant que toute carte planaire peut être colorée en utilisant un maximum de cinq couleurs, en s'appuyant sur les concepts fondamentaux de Kempe. Au cours du siècle suivant, des recherches approfondies et des avancées théoriques visaient à réduire le nombre requis de couleurs à quatre, aboutissant à la preuve définitive du théorème des quatre couleurs en 1976 par Kenneth Appel et Wolfgang Haken. Leur preuve revisite notamment les idées originales de Heawood et Kempe, contournant largement les développements théoriques intermédiaires. Au-delà de la résolution d'un défi mathématique vieux d'un siècle, la preuve du théorème des quatre couleurs est importante en tant que première preuve majeure assistée par ordinateur en mathématiques.

En 1912, George David Birkhoff a introduit le polynôme chromatique comme outil d'analyse des problèmes de coloration ; ce concept a ensuite été généralisé par W. T. Tutte dans le polynôme de Tutte. Les deux polynômes sont reconnus comme des invariants cruciaux dans la théorie des graphes algébriques. Kempe avait déjà mis en évidence des scénarios non planaires plus larges en 1879, conduisant à de nombreuses découvertes ultérieures au début du 20e siècle concernant la généralisation de la coloration des graphes planaires aux surfaces de genre topologique supérieur.

En 1960, Claude Berge a avancé une autre conjecture concernant la coloration des graphes, appelée la conjecture forte des graphes parfaits. Cette proposition a été initialement inspirée par le concept de théorie de l'information de Shannon sur la capacité zéro erreur dans les graphiques. La conjecture est restée non prouvée pendant 40 ans jusqu'en 2002, lorsque Chudnovsky, Robertson, Seymour et Thomas l'ont établie de manière concluante comme le célèbre théorème des graphes parfaits forts.

La coloration des graphiques a été étudiée en tant que problème algorithmique depuis le début des années 1970. Le problème des nombres chromatiques, identifié en 1972, constitue l'un des 21 problèmes NP-complets de Karp. À peu près à la même période, plusieurs algorithmes à temps exponentiel ont été conçus, employant des techniques telles que le retour en arrière et la récurrence de suppression-contraction de Zykov en 1949. Une application principale de la coloration des graphiques, l'allocation de registres dans les compilateurs, a été introduite en 1981.

Définitions et terminologie

Coloration des sommets

Lorsqu'il est utilisé sans autre qualification, une coloration de graphe signifie presque invariablement une coloration appropriée des sommets. Ce processus consiste à attribuer des étiquettes distinctes, ou « couleurs », aux sommets d'un graphique de telle sorte qu'aucun sommet relié par une arête ne partage la même couleur. Par conséquent, les graphiques considérés dans ce contexte sont considérés comme sans boucle, car un sommet avec une boucle (une connexion directe à lui-même) ne peut pas être correctement coloré.

La convention d'utilisation des couleurs pour les étiquettes de sommet trouve ses origines dans la coloration des cartes. Les désignations de couleurs spécifiques, telles que rouge et bleu, ne sont généralement utilisées que lorsque le nombre total de couleurs est petit. Dans la plupart des contextes, il est entendu que ces étiquettes sont tirées de l'ensemble des entiers positifs, {1, 2, 3, ...}.

Une coloration employant au plus k couleurs est appelée une (bonne) k-coloration. Le nombre minimum de couleurs nécessaires pour colorer correctement un graphique G est défini comme son numéro chromatique, communément noté χ(G). La notation γ(G) est parfois utilisée de manière interchangeable, car χ(G) représente également la caractéristique d'Euler d'un graphique. Un graphique auquel on peut attribuer une (bonne) k-coloration est appelé k-colorable, et il est désigné k-chromatique si son numéro chromatique est exactement k. Un sous-ensemble de sommets partageant la même couleur est appelé classe de couleur ; chacune de ces classes forme intrinsèquement un ensemble indépendant. Par conséquent, une k-coloration équivaut à une partition de l'ensemble de sommets en k ensembles indépendants, rendant les termes k-partite et k-colorable synonymes.

Polynôme chromatique

Le polynôme chromatique énumère les différentes façons dont un graphique peut être coloré en utilisant un nombre spécifié de couleurs disponibles. Par exemple, un graphique illustratif peut être coloré de 12 manières lorsque trois couleurs sont utilisées. A l’inverse, avec seulement deux couleurs, aucune coloration valide n’est réalisable. Si quatre couleurs sont disponibles, le graphique peut être coloré de 24 + 4 × 12 = 72 façons. Ce total en représente 4 ! = 24 colorations valides lorsque les quatre couleurs sont utilisées (puisque chaque affectation de quatre couleurs à n'importe quel graphe à 4 sommets constitue une coloration appropriée), en plus de 12 3 colorations valides pour chaque sélection de trois couleurs parmi les quatre disponibles. Ainsi, pour l'exemple de graphique, un tableau détaillant le nombre de colorations valides commencerait comme suit :

Le polynôme chromatique est représenté par la fonction P(G, t), qui quantifie le nombre de t-colorations pour un graphe G. Comme son nom l'indique, pour tout graphe G donné, cette fonction est bien un polynôme dans la variable t. Pour l'exemple de graphique, le polynôme chromatique est P(G, t) = t(t − 1)§2728§(t − 2), et il est confirmé que P(G, 4) = 72.

Le polynôme chromatique offre un aperçu plus complet de la colorabilité du graphique G que le nombre chromatique seul. Plus précisément, χ est défini comme le plus petit entier positif qui n'est pas une racine (zéro) du polynôme chromatique, formellement indiqué comme χ(G) = min{k : P(G, k) > 0}.

Coloration des bords

Une coloration des bords d'un graphique est définie comme une coloration appropriée de ses bords, ce qui implique d'attribuer des couleurs aux bords de telle sorte qu'aucune arête partageant un sommet commun ne reçoive la même couleur. Une coloration des bords utilisant k couleurs est appelée k-edge-coloring et correspond à la tâche de partitionner l'ensemble des bords du graphique en k correspondances distinctes. Le nombre minimum de couleurs requis pour une coloration des bords d'un graphique G est désigné comme son indice chromatique, également connu sous le nom de numéro chromatique de bord, noté χ′(G). Une coloration Tait fait spécifiquement référence à une coloration à 3 arêtes d'un graphe cubique. Le théorème des quatre couleurs peut être énoncé de manière équivalente comme la proposition selon laquelle tous les graphes planaires, cubiques et sans pont possèdent une coloration de Tait.

Coloration totale

Coloration totale implique l'attribution de couleurs aux sommets et des bords d'un graphique. Par convention, une coloration totale non qualifiée est considérée comme appropriée, ce qui implique qu'aucun sommet adjacent, aucune arête adjacente et aucune arête et ses sommets incidents ne partagent la même couleur. Le nombre chromatique total, noté χ″(G), pour un graphique G représente le nombre minimum de couleurs requis pour toute coloration totale de G.

Coloration du visage

Dans le contexte d'un graphe fortement incrusté sur une surface, la coloration des faces constitue le double problème de la coloration des sommets.

Théorie des flux de Tutte

Pour un graphe G avec un fort plongement sur une surface orientable, William T. Tutte a démontré que si un graphe est k-colorable, alors G possède un flux k nulle part nul. Cette équivalence est valable lorsque la surface en question est une sphère.

Coloration sans étiquette

Une coloration non étiquetée d'un graphe est définie comme une orbite d'une coloration sous l'influence du groupe d'automorphisme du graphe. Alors que les couleurs elles-mêmes conservent leurs étiquettes, le graphique lui-même est considéré comme non étiqueté dans ce contexte. Il existe un concept analogue au polynôme chromatique, qui énumère les colorations non étiquetées d'un graphique en utilisant un ensemble fini spécifié de couleurs.

Lorsqu'un graphe colorant sur d sommets est conceptualisé comme un vecteur dans ⁠${\displaystyle \mathbb {Z} ^{d}}$⁠, l'opération d'un automorphisme correspond à une permutation des coefficients au sein de ce vecteur coloration.

Propriétés

Limites supérieures du nombre chromatique

L'attribution de couleurs distinctes à des sommets distincts entraîne systématiquement une coloration appropriée ; par conséquent,

§67§ ≤ χ ( G ) ≤ n . {\displaystyle 1\leq \chi (G)\leq n.}

Seuls les graphiques sans bords se prêtent à une coloration unique. Un graphique complet, noté ${\displaystyle K_{n}}$, comprenant n sommets, nécessite ${\displaystyle \chi (K_{n})=n}$ couleurs. Dans une coloration optimale, au moins une des arêtes m du graphe doit relier chaque paire de classes de couleurs distinctes ; donc,

χ<!-- χ --> ( G ) ( χ<!-- χ --> ( G ) −<!-- − --> §2930§ ) ≤ §3637§ m . {\displaystyle \chi (G)(\chi (G)-1)\leq 2m.}

Plus largement, une famille ${\displaystyle {\mathcal {F}}}$ des graphiques est pris en compte χ-limité si une fonction ${\displaystyle c}$ existe de telle sorte que tout graphe ${\displaystyle G}$ dans ${\displaystyle {\mathcal {F}}}$ peut être coloré en utilisant au maximum ${\displaystyle c(\omega (G))>$ couleurs. Ici, ${\displaystyle \omega (G)>$ désigne le numéro de clique de ${\displaystyle G}$. Pour la famille spécifique des graphiques parfaits, cette fonction est définie comme ${\displaystyle c(\omega (G))=\omega (G)}$.

Les graphiques bicolores sont précisément les graphiques bipartis, une catégorie qui englobe les arbres et les forêts. Selon le théorème des quatre couleurs, tout graphe plan peut être coloré avec un maximum de quatre couleurs.

L'utilisation d'un algorithme de coloration glouton démontre que n'importe quel graphe peut être coloré en utilisant un nombre de couleurs égal à une de plus que son degré de sommet maximum.

Cette relation est formellement exprimée comme ${\displaystyle \chi (G)\leq \Delta (G)+1.}$.

Pour les graphiques complets, le nombre chromatique est ${\displaystyle \chi (G)=n}$ et le degré maximum est Δ<!-- Δ -->(G)=n−<!-- − -->§4950§{\displaystyle \Delta (G)=n-1}. De même, les cycles impairs présentent ${\displaystyle \chi (G)=3}$ et ${\displaystyle \Delta (G)=2}$. Par conséquent, pour ces types de graphiques spécifiques, la limite susmentionnée est optimale. Cependant, dans tous les autres scénarios, cette limite peut être légèrement améliorée, comme l'explique le théorème de Brooks, qui stipule que : 

Théorème de Brooks affirme que ${\displaystyle \chi (G)\leq \Delta (G)}$ pour tout graphe simple et connecté G, à l'exception des graphes complets et des cycles impairs.

Limites inférieures du nombre chromatique

Au fil du temps, diverses limites inférieures pour le nombre chromatique ont été établies :

Si un graphique G possède une clique de taille k, un minimum de k couleurs sera requis pour colorer cette clique spécifique. Cela implique que le nombre chromatique doit être au moins équivalent au numéro de clique :

Le nombre chromatique d'un graphe G, noté χ(G), est toujours supérieur ou égal à son numéro de clique, ω(G), exprimé par l'inégalité {\displaystyle \chi (G)\geq \omega (G).}

Pour des graphiques parfaits, cette limite est précisément respectée. La tâche informatique consistant à identifier les cliques est appelée problème des cliques.

La limite de Hoffman : Considérez ${\displaystyle W}$ comme une véritable matrice symétrique où ses éléments Wi,j=§3839§{\displaystyle W_{i,j}=0} si la paire ${\displaystyle (i,j)>$ ne constitue pas une arête dans le graphique ${\displaystyle G}$. Nous définissons ${\displaystyle \chi _{W}(G)=1-{\tfrac {\lambda _{\max }(W)}{\lambda _{\min }(W)}}}$, où ${\displaystyle \lambda _{\max }(W),\lambda _{\min }(W)}$ représentent les valeurs propres maximales et minimales de ${\displaystyle W}$.Par la suite, ${\textstyle \chi _{H}(G)=\max _{W}\chi _{W}(G)}$ est défini comme la valeur maximale de χW(G) sur toutes ces matrices ${\displaystyle W}$. Cela conduit à la relation suivante :

L'inégalité résultante indique que χH(G) est inférieur ou égal à χ(G), formellement exprimé comme {\displaystyle \chi _{H}(G)\leq \chi (G).}

Nombre chromatique vectoriel : Considérons une matrice semi-définie positive ${\displaystyle W}$ tel que pour chaque arête ${\displaystyle (i,j)}$ dans un graphique ${\displaystyle G}$, l'inégalité Wi,j≤<!-- ≤ -->−<!-- − -->§5152§k−§5960§{\displaystyle W_{i,j}\leq -{\tfrac {1}{k-1}}} tient. Le ${\displaystyle \chi _{V}(G)}$ est défini comme le plus petit entier k pour lequel une telle matrice ${\displaystyle W}$ existe.

Par conséquent, ${\displaystyle \chi _{V}(G)\leq \chi (G).}$

Nombre de Lovász : Le nombre de Lovász d'un graphe complémentaire établit également une limite inférieure pour le nombre chromatique.

Cette relation est exprimée comme suit : ${\displaystyle \vartheta ({\bar {G}})\leq \chi (G).}$

Nombre chromatique fractionnaire : le nombre chromatique fractionnaire d'un graphique fournit de la même manière une limite inférieure pour son nombre chromatique.

Ceci est représenté par l'inégalité : ${\displaystyle \chi _{f}(G)\leq \chi (G).}$

Les limites susmentionnées sont classées hiérarchiquement comme suit :

L'ordre complet est donné par : ${\displaystyle \chi _{H}(G)\leq \chi _{V}(G)\leq \vartheta ({\bar {G}})\leq \chi _{f}(G)\leq \chi (G).}$

Graphiques caractérisés par des nombres chromatiques élevés

Les graphiques possédant de grandes cliques présentent invariablement un nombre chromatique élevé ; cependant, l’inverse n’est pas vrai. Le graphe de Grötzsch en est un exemple, étant un graphe quadrichromatique dépourvu de triangles, une caractéristique qui peut être étendue grâce à la construction des Mycielskiens.

Théorème (W. T. Tutte, 1947 ; Alexander Zykov, 1949 ; Jan Mycielski, 1955) : les graphiques sans triangle peuvent posséder un nombre chromatique arbitrairement élevé.

Pour étayer ce théorème, Mycielski et Zykov ont développé indépendamment des constructions inductives pour des familles de graphes sans triangle qui présentent des nombres chromatiques arbitrairement grands. Par la suite, Burling (1965) a démontré ce phénomène en construisant des boîtes alignées sur les axes dans ${\displaystyle \mathbb {R} ^{3}}$ dont le graphique d'intersection est sans triangle et nécessite un nombre arbitraire de couleurs pour une coloration correcte. Cette famille spécifique de graphiques est connue sous le nom de graphiques de Burling. De plus, Pawlik et al. (2014) ont utilisé cette même classe de graphiques pour construire une famille de segments de droite sans triangle dans le plan, révélant que le nombre chromatique de leur graphique d'intersection est également arbitrairement grand. Par conséquent, cela implique que les deux cases alignées sur les axes dans ${\displaystyle \mathbb {R} ^{3}}$ et segments de ligne dans ${\displaystyle \mathbb {R} ^{2}}$ ne sont pas χ-limités.

Selon le théorème de Brooks, les graphiques caractérisés par un nombre chromatique élevé doivent également posséder un degré maximum élevé. Cependant, la colorabilité n’est pas exclusivement une propriété locale. Par exemple, un graphique avec une circonférence élevée ressemble localement à un arbre en raison de ses cycles étendus, mais son nombre chromatique n'est pas nécessairement 2.

Théorème (Erdős) : des graphiques peuvent exister avec une circonférence et un nombre chromatique arbitrairement élevés.

Limites de l'index chromatique

Une coloration des bords d'un graphe G équivaut à une coloration des sommets de son graphe linéaire ${\displaystyle L(G)}$, et inversement. Par conséquent,

${\displaystyle \chi '(G)=\chi (L(G)).}$

Il existe une corrélation significative entre la colorabilité des bords et le degré maximum d'un graphique, noté ${\displaystyle \Delta (G)>$. Étant donné que toutes les arêtes incidentes à un sommet commun doivent se voir attribuer des couleurs distinctes, il s'ensuit que :

${\displaystyle \chi '(G)\geq \Delta (G).}$

De plus,

Théorème de Kőnig déclare que ${\displaystyle \chi '(G)=\Delta (G)>$ si le graphe G est biparti.

Généralement, cette relation est encore plus robuste que celle établie par le théorème de Brooks pour la coloration des sommets.

Théorème de Vizing : Le théorème de Vizing stipule que tout graphe avec un degré maximum de ${\displaystyle \Delta }$ possède un nombre chromatique de bord égal à ${\displaystyle \Delta >$ ou ${\displaystyle \Delta +1}$.

Propriétés supplémentaires

Un graphe est k-colorable si et seulement s'il admet une orientation acyclique où la longueur maximale du chemin ne dépasse pas k ; ce principe est connu sous le nom de théorème de Gallai-Hasse-Roy-Vitaver (Nešetřil & Ossona de Mendez 2012).

Dans le contexte des graphes planaires, les colorations des sommets présentent une dualité fondamentale avec des flux nulle part nul.

Les connaissances concernant les graphes infinis sont considérablement plus limitées. Les déclarations suivantes représentent deux des rares découvertes concernant la coloration des graphes infinis :

• En supposant l'axiome du choix, si chaque sous-graphe fini d'un graphe infini G est k-colorable, alors le graphe G lui-même est également k-colorable. Ce principe est formalisé sous la forme du théorème de Bruijn-Erdős (de Bruijn & Erdős 1951).
• Un graphique qui permet une n-coloration complète pour toutes les valeurs n supérieures ou égales à n§67§ possède également une coloration complète infinie (Fawcett 1978).

Problèmes non résolus

Comme établi précédemment, l'inégalité ${\displaystyle \omega (G)\leq \chi (G)\leq \Delta (G)+1.}$ tient. Une conjecture proposée par Reed en 1998 postule que le nombre chromatique est fondamentalement plus proche de la limite inférieure, en particulier χ<!-- χ -->(G)≤<!-- ≤ -->⌈ω<!-- ω -->(G)+Δ<!-- Δ -->(G)+§9798§§100101§⌉.{\displaystyle \chi (G)\leq \left\lceil {\frac {\omega (G)+\Delta (G)+1}{2}}\right\rceil .}

Le nombre chromatique du plan, défini par la contiguïté entre des points à une distance unitaire, reste indéterminé, bien qu'il soit connu pour être 5, 6 ou 7. D'autres problèmes non résolus liés au nombre chromatique des graphiques englobent la conjecture de Hadwiger, qui postule que tout un graphe avec un nombre chromatique de k contient un graphe complet sur les sommets k en tant que mineur. Sont également incluses la conjecture d'Erdős – Faber – Lovász, qui établit une limite supérieure pour le nombre chromatique d'unions de graphes complets partageant au plus un sommet commun par paire, et la conjecture d'Albertson, qui suggère que parmi les graphes k-chromatiques, les graphes complets présentent le nombre de croisement minimal.

Lorsque Birkhoff et Lewis ont introduit le polynôme chromatique dans le cadre de leurs efforts pour résoudre le théorème des quatre couleurs, ils ont émis l'hypothèse que pour les graphes planaires ${\displaystyle G}$, le polynôme ${\displaystyle P(G,t)>$ ne présenterait aucun zéro dans l'intervalle ${\displaystyle [4,\infty )>$. Bien qu'il soit établi qu'un tel polynôme chromatique manque effectivement de zéros dans la région ${\displaystyle [5,\infty )}$ et cela P ( G , §106107§ ) ≠<!-- ≠ --> §113114§ {\displaystyle P(G,4)\neq 0} , leur conjecture originale reste non résolue. De plus, la caractérisation de graphes possédant des polynômes chromatiques identiques et l'identification des polynômes chromatiques restent des problèmes ouverts.

Algorithmes

Complexité temporelle polynomiale

Déterminer si un graphique est bicolorable revient à déterminer sa bipartité, une tâche réalisable en temps linéaire grâce à des algorithmes de recherche en largeur ou en profondeur. Pour des graphiques parfaits, le nombre chromatique et une coloration associée peuvent être calculés en temps polynomial en utilisant une programmation semi-définie. De plus, des expressions de forme fermée pour les polynômes chromatiques existent pour diverses classes de graphes, notamment les forêts, les graphes d'accords, les cycles, les roues et les échelles, permettant leur évaluation en temps polynomial.

Lorsqu'un graphe est plan et présente une faible largeur de branche, ou s'il est non plan mais possède une décomposition de branche connue, son polynôme chromatique peut être déterminé en temps polynomial via une programmation dynamique. Généralement, le temps de calcul évolue de manière polynomiale avec la taille du graphique mais de manière exponentielle avec la largeur de sa branche.

Algorithmes exacts

Une approche par force brute pour trouver une coloration k implique d'évaluer chacun des ${\displaystyle k^{n}}$ affectations possibles de k couleurs à n sommets pour vérifier leur légalité. Pour déterminer le nombre chromatique et le polynôme chromatique, cette méthode doit être appliquée pour chaque valeur de ${\displaystyle k=1,\ldots ,n-1}$, ce qui le rend peu pratique pour les graphiques d'entrée, sauf les plus petits.

La détermination de la k-colorabilité peut être obtenue dans une complexité temporelle et spatiale de ${\displaystyle O(2.4423^{n})}$ grâce à l'application d'une programmation dynamique combinée à une limite sur le nombre d'ensembles indépendants maximaux. Alternativement, l'utilisation du principe d'inclusion-exclusion parallèlement à l'algorithme de Yates pour la transformation zêta rapide permet de résoudre la k-colorabilité dans une complexité temporelle de O ( §4344§ n n ) {\displaystyle O(2^{n}n)> pour toute valeur de k. Des algorithmes plus efficaces existent pour la 3-colorabilité et la 4-colorabilité, qui peuvent être décidés dans des complexités temporelles de ${\displaystyle O(1.3289^{n})>$ et ${\displaystyle O(1.7272^{n})>$, respectivement. De plus, des algorithmes aux performances exponentiellement améliorées sont disponibles pour la 5-colorabilité et la 6-colorabilité, ainsi que pour des catégories spécifiques de graphiques, tels que les graphiques clairsemés.

Contraction

L'opération de contraction, notée ${\displaystyle G/uv}$ pour un graphe G, implique la fusion de sommets u et v en un seul nouveau sommet, éliminant ensuite toutes les arêtes qui reliaient auparavant u et v. Les bords initialement incidents à u ou v deviennent incidents à ce nœud fusionné nouvellement formé, désigné comme uv. Cette opération fondamentale est essentielle dans l'analyse théorique des problèmes de coloration des graphes.

Le nombre chromatique adhère à la relation de récurrence suivante :

${\displaystyle \chi (G)={\text{min}}\{\chi (G+uv),\chi (G/uv)\}}$

Cette relation a été établie par Zykov en 1949, où u et v représentent des sommets non adjacents. La notation ${\displaystyle G+uv}$ signifie le graphique formé en ajoutant le bord uv à ${\displaystyle G+uv}$. De nombreux algorithmes exploitent cette récurrence, et la structure informatique dérivée de son évaluation est parfois appelée arbre de Zykov. L'efficacité de ces algorithmes dépend de l'heuristique utilisée pour sélectionner les sommets u et v.

Le polynôme chromatique est également conforme à la relation de récurrence suivante :

${\displaystyle P(G-uv,k)=P(G/uv,k)+P(G,k),>$

Ici, u et v désignent les sommets adjacents, et ${\displaystyle G-uv}$ représente le graphique dont le bord uv a été supprimé. De plus, ${\displaystyle P(G-uv,k)}$ quantifie le nombre de colorations propres distinctes pour le graphe, où les sommets peuvent se voir attribuer des couleurs identiques ou distinctes. Par conséquent, les colorations appropriées peuvent être conceptualisées comme résultant de deux configurations graphiques distinctes. Plus précisément, si les sommets u et v se voient attribuer des couleurs différentes, le scénario équivaut à considérer un graphe où u et v sont adjacents. A l'inverse, si u et v partagent la même couleur, la situation peut être modélisée par un graphe où u et v sont contractés. L'enquête de Tutte sur d'autres propriétés de graphes présentant cette relation de récurrence a finalement conduit à son développement du polynôme de Tutte, une généralisation bivariée du polynôme chromatique.

Ces formulations conduisent à une méthodologie récursive connue sous le nom d'algorithme de suppression-contraction, qui sous-tend de nombreux algorithmes de coloration de graphiques. La complexité informatique de cet algorithme présente une relation de récurrence analogue à celle des nombres de Fibonacci. Par conséquent, dans le pire des cas, sa durée d'exécution est limitée par un facteur polynomial de (§1617§+§2223§§2728§)n+m=O(1.6180n+m){\displaystyle \left({\tfrac {1+{\sqrt {5}}}{2}}\right)^{n+m}=O(1.6180^{n+m})}, où n représente le nombre de sommets et m désigne le nombre d'arêtes. Une analyse plus approfondie peut affiner cette limite à un facteur polynomial de ${\displaystyle t(G)}$, qui signifie le nombre d'arbres couvrant dans le graphique d'entrée. Dans les applications pratiques, des stratégies telles que le branchement et la liaison, ainsi que le rejet de l'isomorphisme du graphe, sont utilisées pour atténuer le nombre d'appels récursifs. Le temps d'exécution réel dépend de l'heuristique choisie pour sélectionner les paires de sommets.

Coloration gourmande

L'algorithme glouton traite les sommets dans une séquence prédéterminée, spécifiquement à partir de v §1011§ {\displaystyle v_{1}} à ${\displaystyle v_{n}}$. Pour chaque sommet ${\displaystyle v_{i}}$, l'algorithme attribue la couleur la plus basse possible qui n'a été utilisée par aucun de ses voisins déjà colorés, en particulier ceux de l'ensemble v §9899§ {\displaystyle v_{1}> , ..., v i −<!-- − --> §125126§ {\displaystyle v_{i-1}> . Une nouvelle couleur n'est introduite que si aucune couleur existante ne convient. L'efficacité de la coloration résultante dépend de l'ordre spécifique des sommets utilisé. Bien qu'il existe un ordre optimal qui donne une coloration gourmande avec le nombre minimum de couleurs, noté ${\displaystyle \chi (G)>$, des colorations gourmandes peuvent également effectuer arbitrairement mal. Par exemple, un graphe couronne avec n sommets est colorable en 2 couleurs, mais un ordre spécifique des sommets peut entraîner une coloration gourmande nécessitant ${\displaystyle n/2}$ couleurs.

Dans le contexte des graphiques d'accords, y compris des instances spécialisées telles que les graphiques d'intervalles et les graphiques d'indifférence, l'algorithme de coloration glouton peut obtenir des colorations optimales dans un temps polynomial. Ceci est accompli en sélectionnant un ordre de sommets qui est l'inverse d'un ordre d'élimination parfait pour le graphique. Bien que les graphes parfaitement ordonnés étendent cette caractéristique, identifier un ordre parfait pour ces graphes est un problème NP-difficile.

Lorsque les sommets sont disposés en fonction de leurs degrés, la coloration gourmande qui en résulte utilise un maximum de max i min { d ( x i ) + §3839§ , i } {\displaystyle {\text{max}}_{i}{\text{ min}}\{d(x_{i})+1,i\}} couleurs, ce qui est au plus supérieur d'une unité au degré maximum du graphique. Cette heuristique particulière est fréquemment appelée algorithme de Welsh-Powell. A l’inverse, une heuristique proposée par Brélaz détermine dynamiquement l’ordre des sommets lors de l’exécution de l’algorithme, en priorisant la sélection du sommet connecté à la plus grande diversité de couleurs. De nombreuses autres heuristiques de coloration de graphiques exploitent de la même manière les principes de coloration gloutonne, en employant des stratégies statiques ou dynamiques pour l'ordre des sommets. Ces méthodes sont collectivement connues sous le nom d'algorithmes de coloration séquentielle.

Le nombre de Grundy d'un graphique est défini comme le nombre maximum de couleurs pouvant être obtenues par l'algorithme glouton, en particulier lorsqu'un ordre de sommets est sélectionné pour maximiser ce nombre.

Algorithmes heuristiques

Parmi les principales heuristiques en temps polynomial pour la coloration des graphiques figurent l'algorithme DSatur et l'algorithme récursif du plus grand premier (RLF).

L'algorithme DSatur, semblable à la méthode de coloration gloutonne, colore séquentiellement les sommets du graphique, en utilisant une nouvelle couleur uniquement lorsque cela est nécessaire. Suite à l'attribution d'une couleur à un sommet, l'algorithme identifie le sommet non coloré avec le nombre maximum de couleurs distinctes dans son voisinage adjacent, colorant ensuite ce sommet. Cette métrique est appelée le degré de saturation pour un sommet spécifique.

En revanche, l'algorithme Recursive Largest First (RLF) procède en construisant de manière itérative chaque classe de couleur. Ce processus implique l'identification d'un ensemble indépendant maximal de sommets dans le graphe grâce à des règles heuristiques spécialisées. Ces sommets identifiés se voient ensuite attribuer la même couleur et sont ensuite supprimés du graphique. Cette séquence d'opérations est réitérée sur le sous-graphe résultant jusqu'à ce que tous les sommets aient été colorés.

La complexité de calcul dans le pire des cas pour DSatur est {\displaystyle O(n^2)}, où {\displaystyle n} désigne le nombre total de sommets dans le graphique. Une implémentation alternative de l'algorithme, utilisant un tas binaire pour gérer les degrés de saturation, atteint une complexité de {\displaystyle O((n+m)\log n)}, où {\displaystyle m} représente le nombre d'arêtes. Cette approche optimisée améliore considérablement les performances des graphiques clairsemés. En comparaison, la complexité globale de RLF est légèrement supérieure à celle de DSatur, enregistrée sous la forme {\displaystyle O(mn)}.

Les algorithmes DSatur et RLF donnent des solutions exactes pour les graphiques bipartis, de cycle et de roue.

Algorithmes parallèles et distribués

Un graphe χ-chromatique est manifestement c-colorable dans le modèle LOCAL déterministe, nécessitant {\displaystyle O(n^{1/\alpha })} tours, où {\displaystyle \alpha =\left\lfloor {\frac {c-1}{\chi -1}}\right\rfloor }. Une limite inférieure correspondante de {\displaystyle \Omega (n^{1/\alpha })} tours a également été établi. Cette limite inférieure reste valable même si l'on considère les systèmes informatiques quantiques capables d'échanger des informations quantiques, en exploitant potentiellement un état intriqué pré-partagé.

Dans le domaine des algorithmes distribués, la coloration des graphiques présente une forte corrélation avec le défi de la rupture de symétrie. Les algorithmes randomisés contemporains démontrent une vitesse supérieure à celle des algorithmes déterministes lorsque le degré maximum Δ est suffisamment grand. Les algorithmes randomisés les plus efficaces exploitent la technique multi-essais développée par Schneider et Wattenhofer.

Dans un graphe symétrique, un algorithme distribué déterministe ne peut pas identifier une coloration de sommet appropriée. Par conséquent, des informations auxiliaires sont nécessaires pour résoudre la symétrie. Une hypothèse courante est que chaque nœud possède initialement un identifiant unique, par exemple issu de l'ensemble {1, 2, ..., n}. Alternativement, cela implique qu'une coloration n est initialement fournie. L'objectif est de réduire le nombre de couleurs de n à, par exemple, Δ + 1. L'emploi d'un plus grand nombre de couleurs, telles que O(Δ) au lieu de Δ + 1, nécessite généralement moins de cycles de communication.

Une implémentation distribuée directe de l'algorithme glouton pour la coloration (Δ + 1) exige une communication Θ(n) dans le pire des cas, car les informations devront peut-être se propager sur l'ensemble du réseau.

Le scénario illustratif le plus simple implique un cycle n. Richard Cole et Uzi Vishkin ont démontré l'existence d'un algorithme distribué qui réduit le nombre de couleurs de n à O(log n) en une seule étape de communication synchrone. L'application répétée de cette procédure permet d'obtenir 3 couleurs pour un cycle n dans les étapes de communication O(log* n), à condition que des identifiants de nœuds uniques soient disponibles.

La fonction log*, connue sous le nom de logarithme itéré, est une fonction à croissance exceptionnellement lente, souvent considérée comme « presque constante ». Par conséquent, les découvertes de Cole et Vishkin ont incité à enquêter sur la faisabilité d'un algorithme distribué en temps constant pour la 3-coloration d'un cycle n. Linial (1992) a par la suite démontré l'impossibilité de cela, établissant que tout algorithme distribué déterministe nécessite Ω(log* n) étapes de communication pour réduire une n-coloration à une 3-coloration dans un n-cycle.

La technique développée par Cole et Vishkin est également applicable aux graphes à degrés bornés arbitraires, avec un temps d'exécution de poly(Δ) + O(log* n). Cette technique a été étendue aux graphes de disques unitaires par Schneider et Wattenhofer. Les algorithmes déterministes les plus rapides pour la coloration (Δ + 1) dans les cas de petit Δ ont été développés par Leonid Barenboim, Michael Elkin et Fabian Kuhn. L'algorithme de Barenboim et al. fonctionne dans une complexité temporelle de O(Δ) + log*(n)/2, ce qui est optimal par rapport à n, car le facteur constant de 1/2 n'est pas améliorable étant donné la limite inférieure établie par Linial. Panconèse & Srinivasan (1996) a utilisé des décompositions de réseau pour calculer une coloration Δ+1 dans le temps §2122§ O ( journal ⁡ n ) {\displaystyle 2^{O\left({\sqrt {\log n}}\right)}} .

Le problème de la coloration des bords a également été étudié dans le modèle distribué. Panconèse & Rizzi (2001) a réalisé une coloration (2Δ − 1) en O(Δ + log* n) en utilisant ce modèle. La limite inférieure établie par Linial (1992) pour la coloration distribuée des sommets est également pertinente pour le problème de coloration distribuée des arêtes.

Algorithmes décentralisés

Les algorithmes décentralisés fonctionnent sans aucun passage de message, contrairement aux algorithmes distribués, qui reposent sur l'échange de messages local. Des algorithmes décentralisés efficaces sont disponibles pour la coloration des graphiques, à condition qu'une coloration appropriée soit réalisable. De tels algorithmes présupposent qu'un sommet puisse détecter si l'un de ses voisins utilise la même couleur, identifiant ainsi un conflit local. Cette prémisse est considérée comme raisonnable dans de nombreuses applications ; par exemple, dans l'attribution de canaux sans fil, il est généralement plausible de supposer qu'une station peut détecter d'autres émetteurs interférents utilisant le même canal (par exemple, via la mesure SINR). Cette entrée sensorielle est adéquate pour que les algorithmes basés sur l'apprentissage d'automates convergent vers une coloration graphique appropriée avec une probabilité de un.

Complexité informatique

La complexité informatique de la coloration des graphiques est importante. Déterminer si un graphe donné permet une k-coloration pour un k spécifié est un problème NP-complet, à l'exception des cas où k ∈ {0,1,2}. Plus précisément, calculer le nombre chromatique est une tâche NP-difficile. Même pour les graphes planaires 4-réguliers, le problème des 3 colorations conserve sa classification NP-complète. À l'inverse, pour les graphes possédant un degré maximum de 3 ou moins, le théorème de Brooks démontre que le problème des 3 colorations peut être résolu en temps linéaire. De plus, le théorème des quatre couleurs garantit l'existence d'une coloration k pour tout graphe planaire lorsque k > 3, et une telle coloration peut être identifiée en temps polynomial. Néanmoins, l'identification de la plus petite coloration lexicographiquement à 4 couleurs pour un graphe planaire constitue un défi NP-complet.

L'algorithme d'approximation le plus efficace actuellement disponible donne une coloration dont la taille est limitée par un facteur d'au plus O(n(log log n)§67§(log n)⁻³) par rapport à l'image chromatique. numéro. De plus, pour tout ε > 0, approximant le nombre chromatique dans un facteur de n^1−ε est classé comme NP-dur.

De plus, il est NP-difficile de colorer un graphique à 3 couleurs en utilisant 5 couleurs, un graphique à 4 couleurs avec 7 couleurs ou un graphique à kcolorable avec ( k ⌊<!-- ⌊ --> k / §2829§ ⌋ ) − §4445§ {\displaystyle \textstyle {\binom {k}{\lfloor k/2\rfloor }}-1} couleurs lorsque k ≥ 5.

Déterminer les coefficients du polynôme chromatique est un problème #P-difficile. En effet, même en calculant la valeur de ${\displaystyle \chi (G,k)>$ s'avère #P-difficile pour toute valeur rationnelle de k, à l'exclusion de k = 1 et k = 2. De plus, aucun schéma d'approximation randomisée entièrement polynomiale (FPRAS) n'existe pour évaluer le polynôme chromatique à tout point rationnel k ≥ 1,5, à la seule exception de k = 2, sauf si les classes de complexité NP et RP sont équivalentes.

Concernant la coloration des bords, le théorème de Vizing fournit une preuve qui donne un algorithme capable d'utiliser un maximum de Δ+1 couleurs. Néanmoins, la détermination entre les deux valeurs potentielles du nombre chromatique des bords est un problème NP-complet. Concernant les algorithmes d'approximation, l'algorithme de Vizing démontre que le nombre chromatique des bords peut être approché avec une précision de 4/3. Parallèlement, un résultat de dureté correspondant indique la non-existence de tout algorithme (4/3 − ε) pour tout ε > 0, sauf si P est égal à NP. Ces résultats représentent certaines des premières contributions au domaine des algorithmes d'approximation, malgré le fait que les publications originales n'employaient pas explicitement cette terminologie spécifique.

Applications

Planification

La coloration des sommets sert de modèle à divers problèmes de planification. Dans sa représentation la plus simple, un ensemble spécifié de tâches doit être alloué à des plages horaires distinctes, chaque tâche exigeant un seul créneau. Bien que les tâches puissent être planifiées dans n'importe quel ordre, certaines paires de tâches peuvent être en conflit, ce qui signifie qu'elles ne peuvent pas occuper le même créneau horaire, souvent en raison de leur dépendance à l'égard d'une ressource commune. Le graphe résultant est construit avec un sommet représentant chaque tâche et une arête reliant chaque paire de tâches en conflit. Le nombre chromatique du graphique correspond précisément au makespan minimum, qui signifie la durée optimale requise pour terminer toutes les tâches sans conflits.

Les caractéristiques spécifiques d'un problème de planification dictent la structure sous-jacente du graphique. Par exemple, dans le contexte de l'attribution d'avions à des horaires de vol, le graphique de conflit généré est un graphique d'intervalle, permettant ainsi une résolution efficace du problème de coloration. De même, pour l'allocation de bande passante entre les stations de radio, le graphe de conflit produit est un graphe de disque unitaire, ce qui rend le problème de coloration 3-approximable.

Allocation de registre

Un compilateur fonctionne comme un programme informatique conçu pour traduire le code source d'un langage de programmation vers un autre. Pour améliorer les performances d'exécution du code généré, l'optimisation du compilateur utilise des techniques telles que l'allocation de registres, qui consiste à stocker les valeurs les plus fréquemment consultées du programme compilé dans les registres à grande vitesse du processeur. Le scénario optimal implique d'attribuer des valeurs aux registres de manière à permettre à toutes les valeurs nécessaires de résider simultanément dans les registres pendant leur utilisation.

Dans la conception d'un compilateur, une approche conventionnelle de ce problème consiste à le modéliser sous la forme d'un problème de coloration de graphe. Plus précisément, le compilateur génère un graphe d'interférence, dans lequel les variables sont représentées sous forme de sommets, et une arête existe entre deux sommets si leurs variables correspondantes sont simultanément actives. Si ce graphique peut être colorié avec k couleurs distinctes, cela implique que tout ensemble concurrent de variables peut être alloué à un maximum de k registres.

Autres applications

Les problèmes de coloration des graphiques se manifestent dans de nombreux domaines pratiques, notamment la programmation sportive, la conception de la disposition des sièges, l'horaire des examens, l'optimisation de la répartition des taxis et la résolution des puzzles Sudoku.

Paradigmes de coloration alternatifs

Théorie de Ramsey

La théorie de Ramsey étudie une catégorie importante de problèmes de coloration impropre, dans lesquels des couleurs sont attribuées aux bords d'un graphe sans imposer de contraintes sur les couleurs des bords incidents. Une illustration fondamentale est le théorème sur les amis et les étrangers, qui postule que dans n'importe quel bord, la coloration de ${\displaystyle K_{6}}$, le graphe complet comprenant six sommets, l'existence d'un triangle monochromatique est garantie. Ce concept est fréquemment illustré en affirmant que tout groupe de six individus contiendra invariablement soit trois étrangers communs, soit trois connaissances communes. La portée plus large de la théorie de Ramsey implique la généralisation de ce principe pour identifier des modèles au sein d'un caractère apparemment aléatoire, établissant ainsi des conditions universelles pour la présence de sous-graphes monochromatiques possédant des propriétés structurelles spécifiques.

Coloration modulaire

La coloration modulaire représente une catégorie distincte de coloration de graphiques où la couleur attribuée à chaque sommet est déterminée par la somme des couleurs de ses sommets voisins.

Considérez ${\displaystyle k\geq 2}$ comme nombre de couleurs disponibles, où ${\displaystyle \mathbb {Z} _{k}}$ désigne l'ensemble des entiers modulo ${\displaystyle k}$, comprenant les éléments (ou couleurs) §6768§ , §7172§ , §7576§ , . . . , k −<!-- − --> §9293§ , k −<!-- − --> §101102§ {\displaystyle 0,1,2,...,k-2,k-1} . Initialement, chaque sommet du graphique ${\displaystyle G}$ se voit attribuer une couleur de l'ensemble Z k {\displaystyle \mathbb {Z} _k}, sans aucune restriction empêchant les sommets adjacents de partager la même couleur. Par conséquent, l'objectif est de définir une fonction de coloration ${\displaystyle c}$ tel que ${\displaystyle c:V(G)\rightarrow \mathbb {Z} _{k}}$, où l'attribution de couleurs identiques aux sommets adjacents est autorisée.

Pour chaque sommet ${\displaystyle v}$ dans un graphique ${\displaystyle G}$, sa somme de couleurs, notée ${\displaystyle v}$, ou plus formellement ${\displaystyle \sigma (v)>$, représente la somme des couleurs de tous les sommets adjacents à ${\displaystyle v}$, calculé modulo ${\displaystyle k}$. Cette somme de couleurs pour ${\displaystyle v}$ est formellement exprimé comme :

${\displaystyle \sigma (v)=\sum _{u\in N(v)}c(u),}$

Ici, ${\displaystyle u}$ désigne tout sommet situé à proximité de ${\displaystyle v}$, représenté par ${\displaystyle N(v)>$. Par la suite, chaque sommet se voit attribuer une nouvelle couleur basée sur la somme des couleurs de ses sommets adjacents. Un graphique ${\displaystyle G}$ est considéré comme possédant un ${\displaystyle k}$-coloration si, pour toute paire de sommets adjacents, tels que ${\displaystyle a}$ et ${\displaystyle b}$, leurs sommes de couleurs respectives sont distinctes, c'est-à-dire ${\displaystyle \sigma (a)\neq \sigma (b)>$.Le nombre chromatique modulaire de ${\displaystyle G}$, noté ${\displaystyle mc(G)>$, est défini comme la plus petite valeur entière de ${\displaystyle k}$ pour lequel un ${\displaystyle k}$-coloration de ${\displaystyle G}$ existe.

Considérez un sommet ${\displaystyle v}$ avec les sommets adjacents affectés aux couleurs §2223§ , §2627§ , §3031§ {\displaystyle 0,1,1} et ${\displaystyle 3{\bmod {4}}}$ (où ${\displaystyle k=4}$). La somme des couleurs résultante est calculée comme suit : σ<!-- σ --> ( v ) = ( §103104§ + §107108§ + §111112§ + §115116§ ) mod §123124§ = §129130§ mod §135136§ = §141142§ mod §147148§ {\displaystyle \sigma (v)=(0+1+1+3){\bmod {4}}=5{\bmod {4}}=1{\bmod {4}}} . Cette valeur devient alors la nouvelle couleur du sommet ${\displaystyle v}$. Ce processus itératif est appliqué à chaque sommet de ${\displaystyle G}$.Si aucun sommet adjacent ne possède des sommes de couleurs identiques, alors ${\displaystyle G}$ est considéré comme ayant un modulo ${\displaystyle 4}$ coloration.

Méthodologies de coloration alternatives

Le concept de coloration s'étend aux graphiques signés et aux graphiques de gain.

Graphique critique

• Graphique critique
• Jeu de coloriage de graphiques
• Homomorphisme graphique
• Construction Hajós
• Mathématiques du Sudoku
• Graphique multipartite
• Graphique colorisable de manière unique

Remarques

Références

GCol : une bibliothèque Python open source conçue pour la coloration de graphiques.

• GCol Une bibliothèque Python open source pour la coloration de graphiques.
• Algorithmes de coloration de graphiques hautes performances : une collection de huit algorithmes distincts (implémentés en C++) présentés dans la publication A Guide to Graph Colouring : Algorithms and Applications (Springer International Publishers, 2015).
• CoLoRaTiOn de Jim Andrews et Mike Fellows constitue un puzzle de coloration graphique.
• Code source pour le calcul efficace des polynômes de Tutte, chromatiques et de flux par Gary Haggard, David J. Pearce et Gordon Royle.
• Code pour calculer efficacement les polynômes de Tutte, chromatiques et de flux Archivé le 16/04/2008 à la Wayback Machine par Gary Haggard, David J. Pearce et Gordon Royle
• Une application Web de coloration de graphiques développée par Jose Antonio Martin H.