Discussion:Coloration de graphe

Réseau PERT : hors contexte

J'ai supprimé l'exemple de réseau P.ER.T qui ne me semblait pas une illustration de la coloration de grapheHB 23 aoû 2004 à 12:34 (CEST)

Merci je me suis complement trompé et j'était partie sur autre chose. Désolé. Lamardelmy

Nombre chromatique : notation(s)

Je fais de la coloration de graphes depuis 4 ans, et je n'ai jamais vu la notation $\gamma (G)$ pour le nombre chromatique auparavant. Il me semble que $\chi (G)$ est utilisé dans la plupart des articles scientifiques, en tout cas... Ouill 7 Oct 2005 à 23h05

$\gamma (G)$ est utilisé par exemple dans [Gondran-Minoux, Graphes et algortihmes, collection de la direction des études et recherches d'électricité de France, 1979, 1985, 1995] phe 4 décembre 2005 à 11:04 (CET)

Oui, dans le Berge de 1970 aussi... un livre français. Reste que tous les articles datant de moins de 10 ans que j'ai pu avoir sous les yeux depuis que je bosse sur la coloration utilisent comme notation $\chi (G)$ pour le nombre chromatique, $\chi '(G)$ pour l'indice chromatique, $\chi _{a}(G)$ pour le nombre chromatique acyclique, $\chi ^{l}(G)$ pour le nombre chromatique par listes... etc Ouill 10 Déc 2005 à 02h50

Bonjour,

Une "précision" semble être apportée implicitement par Claude Berge dans son ouvrage intitulé « Hypergraphes. Combinatoires des ensembles finis » (Bordas, 1987).

On observe en particulier les 3 notations suivantes (chapitre 4 sur les colorations, sélection des pages 112 à 117) :

• γ(G) : nombre chromatique d'un graphe (au sens : hypergraphe dont toutes les arêtes sont de cardinalité 2) ;
• χ(H) : nombre chromatique d'un hypergraphe (au sens littéral) ;
• γ(H) : nombre chromatique fort d'un hypergraphe (égal au nombre chromatique de la 2-section de cet hypergraphe, c'est-à-dire d'un graphe au sens classique — la notation est cohérente avec γ(G)).

Un bon compromis serait probablement le choix de la mention des 2 notations lors de la 1ère occurrence de la notation γ() dans la version actuelle de l'article.

A titre d'information, l'indice chromatique (IC) d'un hypergraphe est noté q(H) dans le même ouvrage (page 14).

Cordialement --nha de Lyon 28 août 2006 à 01:01 (CEST)

Héhé, je pensais que ce débat avait été réglé il y a longtemps. Encore une fois, ces notations sont des notations françaises des années pré 90. Actuellement, en France et partout dans le monde, le $\chi$ est utilisé à 99,9999% par les chercheurs en coloration de graphes pour désigner le nombre chromatique. Je sens que ça va être sans fin... Regardez la page anglaise, la page allemande, ou la page tchèque (les tchèques sont extrémement dynamique au niveau international en théorie des graphes) si vous avez encore besoin d'être convaincu. Ouill 16 Nov 2006 à 17h09

Bonjour à vous, Ouill. Merci pour les références nombreuses sur les habitudes contemporaines de notation du nombre chromatique. Vous n'aviez cependant pas besoin de me convaincre sur ce point. L'adoption de χ m'est parue cohérente et légitime car elle correspond à la notation pour les hypergraphes, qui généralisent les graphes. Mon précédent message a essentiellement servi à re-situer les notations. Par ailleurs je ne vois pas spécialement de débat re-lancé ici. ;-) Ailleurs peut-être... Bonne fin de semaine. --nha de Lyon 16 novembre 2006 à 22:28 (CET)

Un petit mot encore : j'en avais presque oublié la notation dans l'article. Je suggèrerais qu'on la modifie comme vous, Ouill, l'indiquez : remplacer le γ par le χ ; à défaut, qu'on indique les deux notations. Amicalement. --nha de Lyon 16 novembre 2006 à 22:49 (CET)

Ce changement contribuerait aussi à l'homogénéité de la notation inter-wiki. ;-) --nha de Lyon 17 novembre 2006 à 15:11 (CET).

>Merci pour les références nombreuses sur les habitudes contemporaines de notation du nombre chromatique

Je sens comme une pointe d'ironie :) Désolé de mon ton un peu péremptoire dans mon message précédent... je suis juste un peu agacé par le comportement très français qui consiste à adopter (en tout cas dans ces pages) des notations différentes de celles utilisées dans le reste du monde en se référant à des bibles franco-françaises du domaine en question... Ouill 16 Nov 2006 à 23h12

Hum ! Bon, je vous "rassure" tout de suite : je n'étais point ironique — au contraire. J'avais apprécié le fait que vous illustriez votre point de vue avec des références sérieuses — démarche qui n'est pas forcément adoptée par tous les interlocuteurs. ;-) En outre, autant je reconnais que Claude Berge a été à la source de nombreux concepts et résultats de la théorie des (hyper)graphes, autant je ne positionne pas ses ouvrages au rang de "bible". L'esprit critique (pas nécessairement négatif d'ailleurs) reste de rigueur, surtout quand un ouvrage commence à dater. Amicalement --nha de Lyon 17 novembre 2006 à 15:01 (CET)

Citations, sources

L'article est intéressant, mais il faudrait donner quelques références "classiques" en fin d'article. J'ajoute la rubrique et la référence sur le livre de Berge.

Attention, le theoreme de Vizing parle de l'indice chromatique d'un graphe pas de son nombre chromatique.

Erreur dans le Calcul de DSAT

Bonjour,

J'ai l'impression qu'il y a une erreur dans la partie sur le Calcul de DSAT.

Celle-ci indique :

Calcul de DSAT

 Si aucun voisin de v n'est coloré alors
     DSAT(v)=degré(v) 
 sinon
     DSAT(v)= le nombre de couleurs différentes utilisées dans le premier voisinage de v

J'ai l'impression que c'est faux. La fonction DSAT serait tout simplement :

DSAT(v)= nombre de couleurs différentes utilisées dans le premier voisinage de v

Ensuite on changerait la rédaction du 3 dans l'algorithme :

3. Choisir un sommet non coloré de DSAT maximum. S'il y a plusieurs sommets de DSAT maximal : choisir, parmi ces sommets-là, un sommet de degré maximal.

C'est du moins ce que j'ai l'impression en appliquant l'algorithme à quelques exemples. C'est aussi ce qu'il semble y avoir dans l'article de Brélaz.

http://www.dcc.unicamp.br/~rberga/papers/p251-brelaz.pdf

Qu'en pensez-vous ?

Remarque : j'ai exprimé il y a deux jours la même interrogation dans la discussion sur l'article détaillé de DSAT

Aspects algo : un article à part ?

Bonjour,

je crois que je vais developper les aspects algorithmiques du problème, notamment dans le contexte distribué. Ca risque de rendre l'article un peu inhomogène, j'hésite à faire un article détaillé Problème de la coloration de graphe. Qu'en pensez-vous ? --Roll-Morton (discuter) 24 mars 2014 à 16:22 (CET)

J'ai allégé un peu en enlevant le contenu sur DSATUR qui était déjà présent dans l'article dédié. On pourrait créer l'équivalent de greedy coloring (en) pour déplacer aussi l'autre heuristique. --Roll-Morton (discuter) 29 mai 2017 à 10:45 (CEST)

J'ai aussi mis l'algorithme de Wigderson dans un article à part. --Roll-Morton (discuter) 9 avril 2019 à 18:14 (CEST)

Algorithmes quantiques ?

Il serait sans doute utile de présenter des algorithmes quantiques de coloriage de graphe, avec entre autres l'évaluation de leur complexité (apparemment O(n³) pour tout k-coloriage) ou au moins des liens. Si un spécialiste veut bien s'y coller ...

--2A01:E34:EE56:A840:A5C4:527E:63CA:C791 (discuter) 29 juillet 2021 à 22:18 (CEST)== Coloration ou coloriage ? ==

Colorer signifie au sens propre « revêtir de couleur, donner une certaine teinte à quelque chose ». Le résultat est une coloration. Colorier signifie « appliquer des couleurs sur une surface (un dessin, un plan, etc.) ». Le résultat est un coloriage. Il me semble donc que l'on devrait utiliser ici coloriage et non coloration qui n'est qu'une mauvaise traduction du terme anglais coloring. --2A01:E34:EE56:A840:5442:2259:6131:EFBA (discuter) 29 mars 2020 à 19:54 (CEST) Source : http://bdl.oqlf.gouv.qc.ca/bdl/gabarit_bdl.asp?id=2026 — Le message qui précède, non signé, a été déposé par MClerc (discuter), le 24 avril 2020 à 20:05 (CEST)

La traduction du livre de Cormen et al. Introduction à l'algorithmique utilise "Coloration de graphe". Le mieux est de sourcer pour dire que "coloration" Avez-vous des sources fiables pour le mot "Coloriage" ? Bonne soirée. Fschwarzentruber (discuter) 29 mars 2020 à 22:54 (CEST)

---

Une petite recherche sur « coloriage de graphe » montre que certaines institutions françaises et non des moindres, utilisent le terme coloriage. Par exemple (X, ENS) : https://www.ens.psl.eu/sites/default/files/2018_mp_sujet_infoa.pdf — Le message qui précède, non signé, a été déposé par l'IP 2A01:E34:EE56:A840:A5C4:527E:63CA:C791 (discuter), le 29 juillet 2021 à 22:20 (CEST)