Coloration de graphe (arêtes)

Coloration de graphe (arêtes)

Coloration des arêtes d'un graphe

Coloration des arêtes du graphe de Desargues avec trois couleurs.

La coloration des arêtes d’un graphe entre dans la catégorie plus générale des problèmes de coloration de graphes, le but étant d’attribuer une couleur à chaque arête du graphe avec pour principe que deux arêtes ayant un sommet commun n’aient jamais la même couleur, le tout en utilisant le moins de couleurs possibles. La figure ci-contre est un exemple de coloration d’arêtes correcte. On vérifie en effet que chaque sommet ne possède jamais deux arêtes de la même couleur. On remarquera qu’ici, il n’aurait pas été possible d’effectuer la coloration des arêtes du graphe avec moins de trois couleurs différentes.

Sommaire

Définition

Mentionnée sans précision supplémentaire, l’expression « coloration des arêtes d’un graphe » désigne le fait d’attribuer à chaque arête une couleur, de sorte que deux arêtes adjacentes n’aient jamais la même couleur. Ici, deux arêtes adjacentes sont deux arêtes ayant un sommet en commun.

Le nombre minimal de couleurs différentes pouvant être utilisées pour réaliser la coloration des arêtes d’un graphe G est appelé « indice chromatique du graphe » ou « nombre chromatique des arêtes du graphe» : χ′(G), parfois noté χ1(''G'').

Propriétés

Quelques propriétés de χ′(G):

  1. χ′(G) = 1 si et seulement si G est un appariement.
  2. χ′(G) ≥ Δ(G).
  3. χ′(G) ≤ Δ(G) + 1. (Théorème de Vizing)
  4. χ′(G) ≤ Δ(G) + μ(G), où G peut être un multigraphe.
  5. χ′(G) = Δ(G) si G est un graphe biparti. (Théorème de König sur les graphes bipartis)
  6. χ′(G) = Δ(G) si G est simple, planaire et si Δ(G) ≥ 7. (Vizing en 1965 puis Sanders et Zhao en 2001)

Ici, Δ(G) est le degré maximum de G ; et μ(G), sa multiplicité.

Classification des graphes et détermination de leur nombre chromatique

Comme nous l’avons vu plus haut, χ′(G) = Δ(G) ou χ′(G) = Δ(G) + 1. Quand χ′(G) = Δ(G), on dira que G est de « Classe 1 » ; dans le cas contraire, il sera de « Classe 2 ». En 1981, Holyver a prouvé que la détermination de l’appartenance d’un graphe simple à l’une ou l’autre de ces deux classes est un problème NP-complet. Cependant, pour certains cas particuliers, il existe des règles permettant de conclure rapidement. Par exemple, Vizing, en 1965, a établi qu’un graphe simple et planaire est de Classe 1 si son degré maximal est supérieur ou égal à 8. En revanche, il fit remarquer qu’il existait des graphes simples, planaires et de Classe 2 pour lesquels le degré maximal était de 2, 3, 4 ou 5. Des études supplémentaires l’ont amené à formuler la conjecture suivante :

Conjecture de Vizing pour les graphes planaires : Tout graphe simple, planaire, et de degré maximal égal à 6 ou 7, est de Classe 1.

En 2001, Sanders et Zhao ont partiellement démontré cette conjecture. Ils montrèrent que tout graphe simple, planaire et de degré maximal 7, est de Classe 1. Ainsi, il ne reste plus que le cas des graphes simples, planaires et de degré maximal égal à 6.

Cette conjecture trouve une application dans la conjecture de la coloration totale.

Bibliographie

  • Holyer, Ian (1981). The NP-completeness of edge-coloring. SIAM J. Comput. 10, 718–720.
  • Jensen, Tommy R.; Toft, Bjarne (1995). Graph coloring problems. New York: Wiley-Interscience. ISBN 0-471-02865-7.
  • Kőnig, D. (1916). Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre. Mathematische Annalen 77, 453–465.
  • Sanders, Daniel P.; Zhao, Yue (2001). Planar Graphs of Maximum Degree Seven are Class I. Journal of Combinatorial Theory, Series B. 83, Issue 2, 201–212.
  • Vizing, V. G. (1964). On an estimate of the chromatic class of a p-graph. Diskret. Analiz. 3, 25–30.
  • Vizing, V. G. (1965). Critical graphs with given chromatic class (in Russian). Metody Diskret. Analiz. 5, 9–17.
Ce document provient de « Coloration des ar%C3%AAtes d%27un graphe ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Coloration de graphe (arêtes) de Wikipédia en français (auteurs)

Игры ⚽ Нужно сделать НИР?

Regardez d'autres dictionnaires:

  • Coloration De Graphe — En mathématiques, la coloration de graphe renvoie à un champ d études appartenant à la théorie des graphes. Il s agit de déterminer combien de couleurs différentes suffisent pour colorer entièrement un graphe de telle façon qu aucun nœud du… …   Wikipédia en Français

  • Coloration de graphe — En théorie des graphes, colorer un graphe signifie attribuer une couleur à chacun de ses sommets de manière à ce que deux sommets reliés par une arête soient de couleur différente. Est souvent recherchée l utilisation d un nombre minimal de… …   Wikipédia en Français

  • Graphe de Coxeter — Représentation du graphe de Coxeter. Nombre de sommets 28 Nombre d arêtes 42 Distribution des degrés 3 régulier Rayon 4 …   Wikipédia en Français

  • Graphe de Gray — Représentation du graphe de Gray. Nombre de sommets 54 Nombre d arêtes 81 Distribution des degrés 3 régulier Rayon …   Wikipédia en Français

  • Graphe de Folkman — Représentation du graphe de Folkman Nombre de sommets 20 Nombre d arêtes 40 Distribution des degrés 4 régulier Rayon …   Wikipédia en Français

  • Graphe De Coxeter — Le graphe de Coxeter Nombre de sommets 28 Nombre d arêtes 42 Distribution des degrés 3 régulier Diamètre 4 Propriétés Hypohamilton …   Wikipédia en Français

  • Graphe de coxeter — Le graphe de Coxeter Nombre de sommets 28 Nombre d arêtes 42 Distribution des degrés 3 régulier Diamètre 4 Propriétés Hypohamilton …   Wikipédia en Français

  • Graphe (mathématiques) — Théorie des graphes  Pour la notion mathématique utilisée en Théorie des ensembles, voir Graphe d une fonction. La théorie des graphes est une branche commune à l informatique et aux mathématiques étudiant les graphes et les objets qui lui… …   Wikipédia en Français

  • Graphe (théorie des graphes) — Théorie des graphes  Pour la notion mathématique utilisée en Théorie des ensembles, voir Graphe d une fonction. La théorie des graphes est une branche commune à l informatique et aux mathématiques étudiant les graphes et les objets qui lui… …   Wikipédia en Français

  • Coloration des aretes d'un graphe — Coloration des arêtes d un graphe Coloration des arêtes du graphe de Desargues avec trois couleurs. La coloration des arêtes d’un graphe entre dans la catégorie plus générale des problèmes de coloration de graphes, le but étant d’attribuer une… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”