Coloration des arêtes d'un graphe

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Coloration des arêtes du graphe de Desargues avec trois couleurs.

En théorie des graphes et en algorithmique une coloration des arêtes d’un graphe, consiste à attribuer à chaque arêtes une couleur, en évitant que deux arêtes partageant un sommet soient de la même couleur.

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.

Définition[modifier | modifier le code]

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é \chi_1(''G'').

Propriétés[modifier | modifier le code]

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

  1. χ′(G) = 1 si et seulement si G est un couplage.
  2. χ′(G) ≥ Δ(G).
  3. χ′(G) ≤ Δ(G) + 1. (C'est le 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[modifier | modifier le code]

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 recherches 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[modifier | modifier le code]

  • 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.