droite|vignette|upright=1.4| 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 à sommets, et l'algorithme glouton utilise couleurs. Dans l'étude des problèmes de coloration de graphes en mathématiques et en informatique, une coloration gloutonne ou coloration séquentielle 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.

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 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, Theorem 28.33, ; , Algorithm G.

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 colorLa 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, consiste à déterminer les ensembles de sommets de même couleur, une couleur à la fois. Dans cette méthode, chaque classe de couleur est calculée en examinant les sommets dans l'ordre donné. Lorsque ce parcours rencontre un sommet non coloré qui n'a pas de voisin dans , on ajoute à . De cette façon, 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.

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 sommets } et } avec une arête entre à chaque fois qui ) peut être un cas particulièrement mauvais pour la coloration gloutonne : avec l'ordre des sommets , une coloration gloutonne utilise couleurs, une couleur pour chaque paire . Cependant, le nombre optimal de couleurs pour ce graphe est de deux, une couleur pour les sommets et une autre pour les sommets ; .. 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 ; .. 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. 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.

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.

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 ; .. Reconnaître qu'un graphe est parfaitement ordonnable est également NP-complet.

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. 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é et un nombre , s'il existe un ordre des sommets de qui force l'algorithme glouton à utiliser au moins couleurs. En particulier, cela signifie aussi qu'il est difficile de trouver le plus mauvais ordre pour .

Graphes où l'ordre est non pertinent

Les 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. Ces graphes incluent les cographes, qui sont exactement les graphes dans lesquels tous les sous-graphes induits sont bien colorés. Cependant, il est co-NP-complet de déterminer si un graphe est bien coloré.

Si un graphe aléatoire est tiré selon le 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.

Dégénérescence

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 de degré minimum, d'ordonner récursivement le sous-graphe sans le sommet , puis de re placer 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 . 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 » ; .. Cet ordre des sommets et la dégénérescence peuvent être calculés en temps linéaire. 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 ; ..

Avec l'ordre de dégénérescence, la coloration gloutonne utilise au plus couleurs. En effet, chaque sommet, lorsqu'il est coloré, a au plus voisins déjà colorés, donc l'une des 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 . Markossian, Gasparian & Reed (1996) définissent un graphe comme étant -parfait si, pour et chaque sous-graphe induit de , 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 ; .. Tout graphe -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 -parfaits. Si un graphe et son graphe complémentaire sont tous les deux sans trou pair, ils sont tous les deux -parfaits. Les graphes qui sont à la fois des dgraphes parfaits et -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. Sur les graphes de disques unitaires, son rapport d'approximation est de 3. 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.

Ordres adaptatifs