Discussion :

[Kevin12]

bonjour !
je cherche un cours sur les algorithmes de coloration et l'utilisation de la fonction de Grundy.

merci

[c-candide]

bonjour !
je cherche un cours sur les algorithmes de coloration et l'utilisation de la fonction de

Les fonctions de Grundy sont bien expliquées dans le livre de Claude Berge (ou dans le livre un peu ancien mais très bien fait de Jacques Labelle dont on peut trouver une version sur le net en cherchant bien) mais je ne vois pas le rapport avec les problèmes de coloration. Une recherche sur Google semble montrer qu'il n'y a pas de lien "académique" entre les deux notions.

Une recherche sur Google semble montrer qu'il n'y a pas de lien "académique" entre les deux notions.

Il y a bien un rapport mais je crois qu'il est plus ou moins sans intérêt. Ce n'est pas précisé dans le post du PO mais je suppose qu'il parle de coloration des sommets et pas de coloration des arêtes.

Je rappelle ce qu'est une fonction de Grundy sur un graphe orienté G : il s'agit d'une fonction f:G->N={0,1,2,...} telle que pour chaque sommet s de G, f(s) soit le plus des entiers NE figurant PAS parmi les f(v) où v parcourt l'ensemble des voisins de s.

D'abord si f est une fonction de Grundy sur un graphe non orienté G et si q:=max{f(s) ; s dans G} alors il me semble que G admet une (q+1)-coloration car il suffit de colorer chaque sommet s par g(s).

D'autre part, il me semble que la coloration gourmande fournit toujours une fonction de Grundy puisque par définition d'une telle coloration, on colorie un sommet s par la plus petite couleur ne figurant pas parmi les voisins de s déjà colorés.

Comme il est bien connu qu'il existe toujours un ordre tel que l'algorithme gourmand conduise à la coloration optimale, les notions de fonction de coloration et de fonction de Grundy me semblent en l'espèce totalement équivalentes.

EDIT
Coquille, reformulation, orthographe

Par contre, il existe un nombre chromatique de Grundy qui visiblement a été bien étudié (cf. Google : "grundy"" chromatic number") . Il s'agit du nombre maximal de couleurs auquel peut conduire la coloration gourmande (greedy coloring) et si j'ai bien interprété, c'est le max possible des max{g(s); s sommet} lorsque g parcourt l'ensemble des fonctions de Grundy possibles.

EDIT
Mise-en-forme, coquille.

[Kevin12]

Merci c-candide.