Coloration gloutonne

Dans l'étude des problèmes de coloration de graphes en mathématiques et en informatique, une coloration gloutonne ou coloration séquentielle[1] est une coloration des sommets d'un graphe obtenue par un algorithme glouton qui examine les sommets du graphe en séquence et attribue à chaque sommet la première couleur disponible. Les colorations gloutonnes peuvent être obtenues en temps linéaire, mais elles n'utilisent en général pas le nombre minimum possible de couleurs.

Deux colorations gloutonnes du même graphe couronne pour des ordres différents sur les sommets. La numérotation de droite se généralise aux graphes bicolores à

n

sommets, et l'algorithme glouton utilise

n /2

couleurs.

Différents choix pour la suite des sommets produisent généralement des colorations différentes du graphe donné. Une grande partie de l'étude des colorations gloutonnes porte donc sur la façon de trouver un bon ordre. Il existe toujours un ordre qui produit une coloration optimale, et même si l'on trouve aisément pour de nombreuses classes particulières de graphes, ils sont difficiles à trouver en général. Les stratégies couramment utilisées pour l'ordre des sommets impliquent de choisir les sommets de degré élevé avant les sommets de degré inférieur, ou de choisir des sommets avec moins de couleurs disponibles de préférence aux sommets qui sont moins contraints.

Des variantes de coloration gloutonne consistent à choisir les couleurs par un algorithme online, donc sans connaissance de la structure de la partie non colorée du graphe, ou de choisir d'autres couleurs que la première couleur disponible afin de réduire le nombre total de couleurs. Des algorithmes de coloration gloutonne ont été appliqués à des problèmes d'ordonnancement et d'allocation de registres, à l'analyse de jeux combinatoires et aux preuves d'autres résultats mathématiques, notamment le théorème de Brooks sur la relation entre coloration et degré. D'autres concepts de théorie des graphes dérivés des colorations gloutonnes incluent le nombre de Grundy d'un graphe (le plus grand nombre de couleurs que l'on peut trouver dans une coloration gloutonne), et les graphes bien colorés, qui sont les graphes pour lesquels toutes les colorations gloutonnes utilisent le même nombre de couleurs.

Algorithme

La coloration gloutonne pour un ordre de sommets donné peut être calculée par un algorithme qui s'exécute en temps linéaire. L'algorithme traite les sommets dans l'ordre donné, en attribuant une couleur à chacun au fur et à mesure qu'il est traité. Les couleurs peuvent être représentées par les entiers $0,1,2,\dots$ et chaque sommet reçoit la couleur qui est le plus petit entier qui n'est pas déjà utilisé par l'un de ses voisins. Pour trouver la plus petite couleur disponible, on peut utiliser un tableau qui compte le nombre de voisins de chaque couleur (ou qui représente l'ensemble des couleurs des voisins), puis parcourir le tableau pour trouver l'indice de sa première valeur nulle[2].

En langage Python, l'algorithme peut être exprimé sous la forme suivante :

def first_available(color_list):
  """Calcule le plus petit entier naturel qui n'est pas dans la liste des couleurs."""
  color_set = set(color_list)
  count = 0
  while True:
    if count not in color_set:
      return count
    count += 1
def greedy_color(G, order):
  """Détermine la coloration gloutonne de G pour l'ordre donné. 
  La représentation de G est supposée être comme dans https://www.python.org/doc/essays/graphs/
  et doit permettre les parcours des voisins d'un sommet par une boucle de la forme "for w in G[node]".
  La valeur calculée est un dictionnaire qui associe à chaque sommet sa couleur."""
  color = dict()
  for node in order:
    used_neighbour_colors = [color[nbr] for nbr in G[node]
                            if nbr in color]
    color[node] = first_available(used_neighbour_colors)
  return color

La procédure first_available prend un temps proportionnel à la longueur de sa liste d'arguments, car il effectue deux boucles, une sur la liste elle-même et une sur une liste des couleurs de même longueur. Le temps global de l'algorithme de coloration est dominé par les appels à ce sous-programme. Chaque arête du graphe contribue à un seul de ces appels, celui de l'extrémité de l'arête qui se trouve le plus loin dans l'ordre des sommets. Par conséquent, la somme des longueurs des listes d'arguments jusqu'à first_available et le temps total de l'algorithme sont proportionnels au nombre d'arêtes du graphe.

Un autre algorithme, produisant la même coloration[3], consiste à déterminer les ensembles de sommets de même couleur, une couleur à la fois. Dans cette méthode, chaque classe de couleur $C$ est calculée en examinant les sommets dans l'ordre donné. Lorsque ce parcours rencontre un sommet non coloré $v$ qui n'a pas de voisin dans $C$ , on ajoute $v$ à $C$ . De cette façon, $C$ devient un stable maximal parmi les sommets qui n'ont pas encore reçu des couleurs plus petites. L'algorithme trouve ainsi itérativement les classes de couleurs jusqu'à ce que tous les sommets soient colorés. Cependant, cette méthode demande plusieurs parcours du graphe, un parcours pour chaque classe de couleur, au lieu de la méthode décrite ci-dessus qui n'utilise qu'un seul parcours[4].

Choix de l'ordre

Des ordres différents pour les sommets d'un graphe peuvent conduire la coloration gloutonne à utiliser des nombres différents de couleurs, allant du nombre optimal de couleurs à, dans certains cas, un nombre de couleurs proportionnel au nombre de sommets du graphe. Par exemple, un graphe couronne (qui est un graphe formé de deux ensembles disjoints de $n /2$ sommets ${a 1, a 2, ...$ } et ${b 1, b 2, ...$ } avec une arête entre $a i$ à $b j$ chaque fois qui $i \neq j$ ) peut être un cas particulièrement mauvais pour la coloration gloutonne : avec l'ordre des sommets $a 1, b 1, a 2, b 2, ...$ , une coloration gloutonne utilise $n /2$ couleurs, une couleur pour chaque paire $(a i, b i)$ . Cependant, le nombre optimal de couleurs pour ce graphe est de deux, une couleur pour les sommets $a i$ et une autre pour les sommets $b i$ [5]. Il existe aussi des graphes tels qu'avec une probabilité élevée, un ordre de sommets choisi au hasard conduit à un nombre de couleurs beaucoup plus grand que le minimum[6]. Par conséquent, il importe de choisir avec soin l'ordre des sommets pour une coloration gloutonne.

Bons ordres

Les sommets d'un graphe peuvent toujours être ordonnés de telle sorte que l'algorithme glouton produise une coloration optimale ; en effet, étant donné une coloration optimale, on peut ordonner les sommets par leurs couleurs puis, lorsqu'on utilise un algorithme glouton avec cet ordre, la coloration résultante est automatiquement optimale[7]. Cependant, parce que la coloration optimale d'un graphe est un problème NP-complet, tout sous-problème qui permettrait de résoudre ce problème rapidement, y compris la recherche d'un ordre optimal pour la coloration gloutonne, est NP-difficile[8].

Dans les graphes d'intervalles et les graphes cordaux, si les sommets sont ordonnés dans l'ordre opposé de l'ordre d'élimination parfait, alors les voisins précédent chaque sommet forment une clique. Cette propriété a pour effet que la coloration gloutonne produit une coloration optimale, car elle n'utilise jamais plus de couleurs qu'il n'en faut pour chacune de ces cliques. Un ordre d'élimination peut être trouvé en temps linéaire, lorsqu'il existe[9].

Mieux encore, tout ordre d'élimination parfait est héréditairement optimal, ce qui signifie qu'il est optimal à la fois pour le graphe lui-même et pour tous ses sous-graphes induits. Les graphes parfaitement ordonnables (qui incluent les graphes cordaux, les graphes de comparabilité et les graphes à distance héréditaire) sont par définition les graphes qui ont un ordre héréditairement optimal[10]. Reconnaître qu'un graphe est parfaitement ordonnable est également NP-complet[11].

Ordre mauvais

Le nombre de couleurs produites par la coloration gloutonne pour le plus mauvais des ordres d'un graphe donné est appelé son nombre de Grundy[12]. Trouver un bon ordre des sommets pour une coloration gloutonne est difficile, et il en est de même pour trouver un mauvais ordre des sommets. Il est NP-complet de déterminer, pour un graphe donné $G$ et un nombre $k$ , s'il existe un ordre des sommets de $G$ qui force l'algorithme glouton à utiliser au moins $k$ couleurs. En particulier, cela signifie aussi qu'il est difficile de trouver le plus mauvais ordre pour $G$ [12].

Graphes où l'ordre est non pertinent

Les graphes bien colorés (en) sont les graphes pour lesquels toutes les colorations de sommets produisent le même nombre de couleurs. Dans ces graphes, ce nombre est égal à la fois au nombre chromatique et au nombre de Grundy[12]. Ces graphes incluent les cographes, qui sont exactement les graphes dans lesquels tous les sous-graphes induits sont bien colorés[13]. Cependant, il est co-NP-complet de déterminer si un graphe est bien coloré[12].

Si un graphe aléatoire est tiré selon le modèle d'Erdős-Rényi (en) avec une probabilité constante pour l'inclusion de chaque arête, alors tout ordre des sommets choisi indépendamment des arêtes du graphe conduit à une coloration dont le nombre de couleurs est proche du double de la valeur optimale avec grande probabilité. On ne sait pas s'il existe une méthode en temps polynomial pour trouver des colorations sensiblement meilleures pour ces graphes[3].

Dégénérescence

Le prisme triangulaire et l'anti-prisme carré sont des graphes pour lesquels la coloration gloutonne avec l'ordre dégénéré donne un nombre de couleurs plus grand que le nombre optimal.

Comme il est difficile de trouver un ordre optimal des sommets, des heuristiques ont été utilisées pour tenter de réduire le nombre de couleurs sans garantir un nombre optimal de couleurs. Un ordre couramment utilisé pour la coloration gloutonne est de choisir un sommet $v$ de degré minimum, d'ordonner récursivement le sous-graphe sans le sommet $v$ , puis de re placer $v$ comme dernier dans l'ordre. Le plus grand des degrés d'un sommet supprimé que cet algorithme rencontre est appelé la dégénérescence du graphe, et est notée $d$ . Dans le contexte de la coloration gloutonne, la même stratégie d'ordonnancement est également appelée « ordre avec le plus petit en dernier »[14]. Cet ordre des sommets et la dégénérescence peuvent être calculés en temps linéaire[15]. Il peut être considéré comme une version améliorée d'une méthode antérieure appelée la « stratégie du plus grand d'abord » qui trie les sommets dans l'ordre décroissant de leurs degrés[16].

Avec l'ordre de dégénérescence, la coloration gloutonne utilise au plus $d + 1$ couleurs. En effet, chaque sommet, lorsqu'il est coloré, a au plus $d$ voisins déjà colorés, donc l'une des $d + 1$ couleurs est libre pour son utilisation. La coloration gloutonne avec l'ordre de dégénérescence peut trouver des colorations optimales pour certaines classes de graphes, y compris les arbres, les pseudo-forêts et les graphes en couronne [17]. Markossian, Gasparian & Reed (1996)[18] définissent un graphe $G$ comme étant $\beta$ -parfait si, pour $G$ et chaque sous-graphe induit de $G$ , le nombre chromatique est égal à la dégénérescence plus un. Pour ces graphes, l'algorithme glouton avec l'ordre de dégénérescence est toujours optimal[19]. Tout graphe $\beta$ -parfait doit être un graphe sans trou pair, car les cycles pairs ont un nombre chromatique égal à deux et une dégénérescence égale à deux, et ne satisfont pas à l'égalité dans la définition des graphes $\beta$ -parfaits. Si un graphe et son graphe complémentaire sont tous les deux sans trou pair, ils sont tous les deux $\beta$ -parfaits. Les graphes qui sont à la fois des dgraphes parfaits et $\beta$ -parfaits sont exactement les graphes cordaux. Sur les graphes sans trou pair plus généralement, l'ordre de dégénérescence se rapproche de la coloration optimale à au plus le double du nombre optimal de couleurs : son rapport d'approximation est de 2[18]. Sur les graphes de disques unitaires, son rapport d'approximation est de 3[20]. Le prisme triangulaire est le plus petit graphe pour lequel l'un de ses ordres de dégénérescence conduit à une coloration non optimale, et le l'antiprisme carré est le plus petit graphe qui ne peut pas être coloré de manière optimale en utilisant l'un de ses ordres de dégénérescence[17].

Ordres adaptatifs

Brélaz (1979) propose une stratégie, qu'il appelle DSatur, pour l'ordonnancement des sommets dans la coloration gloutonne qui intercale la construction de l'ordonnancement avec le processus de coloration. Dans sa version de l'algorithme de coloration gloutonne, le sommet suivant à colorier à chaque étape est celui qui a le plus grand nombre de couleurs distinctes dans son voisinage. En cas d'égalité, un sommet de degré maximal dans le sous-graphe des sommets non colorés est choisi parmi les sommets liés. En gardant la trace des ensembles de couleurs voisines et de leurs cardinalités à chaque étape, il est possible d'implémenter cette méthode en temps linéaire.

Cette méthode permet de trouver les colorations optimales pour les graphes bipartis[21],, les graphes cactus, les graphes roues, les graphes à au plus six sommets, et presque tous les graphes $k$ -colorables[22]. Lévêque et Maffray[23] ont affirmé en 2005 que cette méthode permet aussi de trouver des colorations optimales pour les graphes de Meyniel (en), mais ils ont plus tard trouvé un contre-exemple[23].

Autres schémas de sélection de couleurs

Il est possible de définir des variantes de l'algorithme de coloration gloutonne dans lesquelles les sommets du graphe donné sont colorés séquentiellement mais dans lesquels la couleur choisie pour chaque sommet n'est pas nécessairement la première couleur disponible. Ces variantesiincluent des méthodes dans lesquelles la partie non colorée du graphe est inconnue de l'algorithme, ou dans lesquelles l'algorithme dispose d'une certaine liberté pour faire des choix de coloration meilleurs que ne le ferait l'algorithme glouton de base.

Sélection en ligne

Des variantes de stratégies de sélection de couleurs ont été étudiées dans le cadre des algorithmes en ligne. Dans ce cas, les sommets d'un graphe sont présentés un par un dans un ordre arbitraire à un algorithme de coloration ; l'algorithme ne peut choisir une couleur pour chaque sommet uniquement sur la base des couleurs et des contiguïtés parmi les sommets déjà traités. Dans ce contexte, on mesure la qualité d'une stratégie de sélection de couleurs par son rapport de compétitivité qui est le rapport entre le nombre de couleurs qu'il utilise et le nombre optimal de couleurs pour le graphe donné[24].

Sans autre restriction sur le graphe, le rapport de compétitivité optimal n'est que légèrement sous-linéaire[25]. Pour les graphes d'intervalles, un ratio constant est possible[26], tandis que pour les graphes bipartis et les graphes creux, un rapport logarithmique peut être atteint. En effet, pour les graphes creux, la stratégie standard de coloration gloutonne qui consiste à choisir la première couleur disponible permet d'atteindre ce rapport compétitif, et il est possible de prouver une limite inférieure correspondante sur le rapport compétitif de tout algorithme de coloration en ligne[24].

Coloration parcimonieuse

Une coloration parcimonieuse, pour un graphe et un ordre des sommets donnés, est par définition une coloration produite par un algorithme glouton qui colorie les sommets dans l'ordre donné, et qui n'introduit une nouvelle couleur que lorsque toutes les couleurs précédentes sont adjacentes au sommet donné, mais l'algorithme peut choisir laquelle des couleurs utiliser (au lieu de toujours choisir la plus petite) lorsqu'il est capable de réutiliser une couleur existante. Le nombre chromatique ordonné est le plus petit nombre de couleurs que l'on peut obtenir de cette manière pour l'ordonnancement donné, et le nombre ochromatique est le plus grand nombre chromatique ordonné parmi toutes les colorations de sommets d'un graphe donné. Malgré sa définition différente, le nombre ochromatique est toujours égal au nombre de Grundy[27].

Applications

La coloration gloutonne, comme elle est rapide et, dans de nombreux cas, n'utilise que peu de couleurs, peut être utilisée dans des applications où une coloration bonne sans être optimale est souhaitée. L'une des premières applications de l'algorithme glouton concerne des problèmes tels que l'ordonnancement des travaux, dans lequel une collection de tâches doit être affectée à un ensemble donné de créneaux horaires, en évitant que des tâches incompatibles ne soient affectées au même créneau horaire[4]. Elle peut aussi être utilisée dans les compilateurs pour l'allocation de registres, en l'appliquant à un graphe dont les sommets représentent les valeurs à affecter aux registres et dont les arêtes représentent les conflits entre deux valeurs qui ne peuvent être affectées au même registre[28]. Dans de nombreux cas, ces graphes d'interférence sont des graphes cordaux, ce qui permet de produire une affectation optimale des registres par coloration gloutonne[29].

En théorie des jeux combinatoires, pour un jeu impartial donné sous la forme d'un graphe acyclique orienté dont les sommets représentent les positions du jeu et les arêtes les mouvements valides d'une position à l'autre, l'algorithme de coloration gloutonne (utilisant l'inverse d'un ordre topologique du graphe) calcule la valeur de Nim de chaque position. Ces valeurs peuvent être utilisées pour déterminer le jeu optimal dans tout jeu unique ou toute somme disjonctive de jeux[30].

Pour un graphe de degré maximal $Δ$ , toute coloration gloutonne utilise au plus $Δ + 1$ couleurs. Le théorème de Brooks dit qu'à deux exceptions près, à savoir des cliques et des cycles impairs, au plus $Δ$ couleurs sont nécessaires. Une preuve du théorème de Brooks consiste à trouver un ordonnancement des sommets dans lequel les deux premiers sommets sont adjacents au dernier sommet sans être adjacents entre eux, et tel que chaque sommet autre que le dernier a au moins un voisin suivant. Pour un tel ordonnancement, l'algorithme de coloration glouton utilise au plus $Δ$ couleurs[31].

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Greedy coloring » (voir la liste des auteurs).

Mitchem (1976).
Hoàng et Sritharan 2016, Theorem 28.33, p. 738 ; Husfeldt 2015, Algorithm G
Frieze et McDiarmid (1997).
Welsh et Powell (1967).
Johnson 1974 ; Husfeldt 2015.
Kučera 1991 ; Husfeldt 2015.
Husfeldt (2015).
Maffray (2003).
Rose, Lueker et Tarjan (1976).
Chvátal 1984 ; Husfeldt 2015.
Middendorf et Pfeiffer (1990).
Zaker (2006).
Christen et Selkow (1979).
Mitchem 1976 ; Husfeldt 2015.
Matula et Beck (1983).
Welsh et Powell 1967 ; Husfeldt 2015.
Kosowski et Manuszewski (2004).
Markossian, Gasparian et Reed (1996).
Markossian, Gasparian et Reed 1996 ; Maffray 2003.
Gräf, Stumpf et Weißenfels (1998).
Brélaz (1979).
Janczewski et al. (2001).
Lévêque et Maffray (2005).
Irani (1994).
Lovász, Saks et Trotter 1989 ; Vishwanathan 1992.
Kierstead et Trotter (1981).
Simmons 1982 ; Erdős et al. 1987.
Poletto et Sarkar 1999. Poletto et Sarkar décrivent leur méthode d'allocation de registres comme n'étant pas basée sur la coloration de graphes, mais elle semble être la même que la coloration gloutonne.
Pereira et Palsberg (2005).
Décrit par exemple dans la section 1.1 de Nivasch 2006.
Lovász (1975).

Bibliographie

Daniel Brélaz, « New methods to color the vertices of a graph », Communications of the ACM, vol. 22, n^o 4,‎ avril 1979, p. 251–256 (DOI 10.1145/359094.359101)
Claude A. Christen et Stanley M. Selkow, « Some perfect coloring properties of graphs », Journal of Combinatorial Theory, series B, vol. 27, n^o 1,‎ 1979, p. 49–59 (DOI 10.1016/0095-8956(79)90067-4, MR 539075)
Vašek Chvátal, « Perfectly orderable graphs », dans Claude Berge et Vašek Chvátal (éditeurs), Topics in Perfect Graphs, Amsterdam, North-Holland, coll. « Annals of Discrete Mathematics » (n^o 21), 1984, p. 63–68. Cité par Maffray 2003.
P. Erdős, W. R. Hare, S. T. Hedetniemi et R. Laskar, « On the equality of the Grundy and ochromatic numbers of a graph », Journal of Graph Theory, vol. 11, n^o 2,‎ 1987, p. 157–159 (DOI 10.1002/jgt.3190110205, MR 889347, lire en ligne).
Alan M. Frieze et Colin McDiarmid, « Algorithmic theory of random graphs », Random Structures & Algorithms, vol. 10, n^os 1–2,‎ 1997, p. 5–42 (DOI 10.1002/(SICI)1098-2418(199701/03)10:1/2<5::AID-RSA2>3.3.CO;2-6, MR 1611517).
Albert Gräf, Michael P. H. Stumpf et Gerhard Weißenfels, « On coloring unit disk graphs », Algorithmica, vol. 20, n^o 3,‎ 1998, p. 277–293 (DOI 10.1007/PL00009196, MR 1489033).
Chinh T. Hoàng et R. Sritharan, « Chapter 28. Perfect Graphs », dans Krishnaiyan Thulasiraman, Subramanian Arumugam, Andreas Brandstädt et Takao Nishizeki (éditeurs), Handbook of Graph Theory, Combinatorial Optimization, and Algorithms, CRC Press, coll. « Chapman & Hall/CRC Computer and Information Science Series » (n^o 34), 2016 (ISBN 9781420011074), p. 707–750.
Thore Husfeldt, « Graph colouring algorithms », dans Lowell W. Beineke et Robin J. Wilson, Topics in Chromatic Graph Theory, Cambridge University Press, coll. « Encyclopedia of Mathematics and its Applications » (n^o 156), 2015 (MR 3380176, arXiv 1505.05825), p. 277–303
Sandy Irani, « Coloring inductive graphs on-line », Algorithmica, vol. 11, n^o 1,‎ 1994, p. 53–72 (DOI 10.1007/BF01294263, MR 1247988).
R. Janczewski, M. Kubale, K. Manuszewski et K. Piwakowski, « The smallest hard-to-color graph for algorithm DSATUR », Discrete Mathematics, vol. 236, n^os 1–3,‎ 2001, p. 151–165 (DOI 10.1016/S0012-365X(00)00439-8, MR 1830607).
H. A. Kierstead et W. T. Trotter, « An extremal problem in recursive combinatorics », Congressus Numerantium, vol. 33 « Proceedings of the Twelfth Southeastern Conference on Combinatorics, Graph Theory and Computing, Vol. II (Baton Rouge, La., 1981) »,‎ 1981, p. 143–153 (MR 0681909). As cited by Irani 1994.
Adrian Kosowski et Krzysztof Manuszewski, « Classical coloring of graphs », dans Marek Kubale (éditeur), Graph Colorings, Providence, Rhode Island, American Mathematical Society, coll. « Contemporary Mathematics » (n^o 352), 2004 (DOI 10.1090/conm/352/06369, MR 2076987), p. 1–19
Luděk Kučera, « The greedy coloring is a bad probabilistic algorithm », Journal of Algorithms, vol. 12, n^o 4,‎ 1991, p. 674–684 (DOI 10.1016/0196-6774(91)90040-6, MR 1130323).
David S. Johnson, « Worst case behavior of graph coloring algorithms », Congressus Numerantium, Winnipeg, Manitoba, Utilitas Math., vol. X « Proceedings of the Fifth Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1974) »,‎ 1974, p. 513–527 (MR 0389644).
Benjamin Lévêque et Frédéric Maffray, « Coloring Meyniel graphs in linear time », Electronic Notes in Discrete Mathematics, Elsevier, vol. 22 « 7th International Colloquium on Graph Theory (ICGT '05), 12–16 September 2005, Hyeres, France »,‎ octobre 2005, p. 25–28 (DOI 10.1016/j.endm.2005.06.005, arXiv cs/0405059, lire en ligne). Voir aussi Benjamin Lévêque et Frédéric Maffray, « Erratum : MCColor is not optimal on Meyniel graphs », hal-archives ouvertes,‎ 9 janvier 2006 (arXiv cs/0405059, HAL hal-00001574v4).
L. Lovász, « Three short proofs in graph theory », Journal of Combinatorial Theory, series B, vol. 19, n^o 3,‎ 1975, p. 269–271 (DOI 10.1016/0095-8956(75)90089-1, MR 0396344).
L. Lovász, M. E. Saks et W. T. Trotter, « An on-line graph coloring algorithm with sublinear performance ratio », Discrete Mathematics, vol. 75, n^os 1–3,‎ 1989, p. 319–325 (DOI 10.1016/0012-365X(89)90096-4, MR 1001404).
Frédéric Maffray, « On the coloration of perfect graphs », dans Bruce Reed et Cláudia L. Sales (éditeurs), Recent Advances in Algorithms and Combinatorics, Springer-Verlag, coll. « CMS Books in Mathematics » (n^o 11), 2003 (ISBN 0-387-95434-1, DOI 10.1007/0-387-22444-0_3, MR 1952983), p. 65–84.
S. E. Markossian, G. S. Gasparian et B. A. Reed, « β-perfect graphs », Journal of Combinatorial Theory, series B, vol. 67, n^o 1,‎ 1996, p. 1–11 (DOI 10.1006/jctb.1996.0030, MR 1385380).
David W. Matula, « A min-max theorem for graphs with application to graph coloring », SIAM Review, vol. 10, n^o 4,‎ 1968, p. 481–482 (SIAM 1968 National Meeting) (DOI 10.1137/1010115).
David W. Matula et L. L. Beck, « Smallest-last ordering and clustering and graph coloring algorithms », Journal of the ACM, vol. 30, n^o 3,‎ 1983, p. 417–427 (DOI 10.1145/2402.322385, MR 0709826).
Matthias Middendorf et Frank Pfeiffer, « On the complexity of recognizing perfectly orderable graphs », Discrete Mathematics, vol. 80, n^o 3,‎ 1990, p. 327–333 (DOI 10.1016/0012-365X(90)90251-C, MR 1049253).
John Mitchem, « On various algorithms for estimating the chromatic number of a graph », The Computer Journal, vol. 19, n^o 2,‎ 1976, p. 182–183 (DOI 10.1093/comjnl/19.2.182, MR 0437376).
Gabriel Nivasch, « The Sprague–Grundy function of the game Euclid », Discrete Mathematics, vol. 306, n^o 21,‎ 2006, p. 2798–2800 (DOI 10.1016/j.disc.2006.04.020, MR 2264378).
Fernando Magno Quintão Pereira et Jens Palsberg, « Register allocation via coloring of chordal graphs », dans Kwangkeun Yi (éditeur), Programming Languages and Systems: Third Asian Symposium, APLAS 2005, Tsukuba, Japan, November 2–5, 2005, Proceedings, Springer, coll. « Lecture Notes in Computer Science » (n^o 3780), 2005 (DOI 10.1007/11575467_21), p. 315–329
Massimiliano Poletto et Vivek Sarkar, « Linear scan register allocation », ACM Transactions on Programming Languages and Systems, vol. 21, n^o 5,‎ septembre 1999, p. 895–913 (DOI 10.1145/330249.330250).
Donald J. Rose, George Lueker et Robert E. Tarjan, « Algorithmic aspects of vertex elimination on graphs », SIAM Journal on Computing, vol. 5, n^o 2,‎ 1976, p. 266–283 (DOI 10.1137/0205021, MR 0408312).
Amin Saberi et David Wajc, « The greedy algorithm is not optimal for on-line edge coloring », dans N. Bansal, E. Merelli et J. Worrell (éditeurs), 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), Schloss Dagstuhl, coll. « Leibniz International Proceedings in Informatics (LIPIcs) » (n^o 198), 2021 (DOI 10.4230/LIPIcs.ICALP.2021.109, lire en ligne), p. 109:1-109:18
Gustavus J. Simmons, « The ordered chromatic number of planar maps », Congressus Numerantium, vol. 36 « Proceedings of the thirteenth Southeastern conference on combinatorics, graph theory and computing (Boca Raton, Fla., 1982) »,‎ 1982, p. 59–67 (MR 726050)
Maciej M. Sysło, « Sequential coloring versus Welsh–Powell bound », Discrete Mathematics, vol. 74, n^os 1–2,‎ 1989, p. 241–243 (DOI 10.1016/0012-365X(89)90212-4, MR 0989136).
George Szekeres et Herbert S. Wilf, « An inequality for the chromatic number of a graph », Journal of Combinatorial Theory, vol. 4,‎ 1968, p. 1–3 (DOI 10.1016/S0021-9800(68)80081-X).
Sundar Vishwanathan, « Randomized online graph coloring », Journal of Algorithms, vol. 13, n^o 4,‎ 1992, p. 657–669 (DOI 10.1016/0196-6774(92)90061-G, MR 1187207).
Dominic J. A. Welsh et M. B. Powell, « An upper bound for the chromatic number of a graph and its application to timetabling problems », The Computer Journal, vol. 10, n^o 1,‎ 1967, p. 85–86 (DOI 10.1093/comjnl/10.1.85).
Manouchehr Zaker, « Results on the Grundy chromatic number of graphs », Discrete Mathematics, vol. 306, n^os 2–3,‎ 2006, p. 3166–3173 (DOI 10.1016/j.disc.2005.06.044, MR 2273147).

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.