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ête une couleur, en évitant que deux arêtes ayant une extrémité commune soient de la même couleur.

La figure ci-contre est un exemple de coloration d'arêtes correcte. On vérifie en effet qu'aucun sommet n'est commun à deux arêtes de même couleur. On remarquera qu'ici, il n'aurait pas été possible de colorer les arêtes du graphe avec seulement deux couleurs.

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 (c'est-à-dire ayant une extrémité commune) n'aient jamais la même couleur. (C'est une notion duale de celle de coloration des sommets d'un graphe.)

Le nombre minimal de couleurs nécessaire pour réaliser la coloration des arêtes d'un graphe G est appelé indice chromatique de G ou nombre chromatique des arêtes de G et noté χ′(G), ou parfois χ1(G). Il ne doit pas être confondu avec le nombre chromatique (des sommets) de G, noté χ(G).

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

Si Δ(G) est le degré maximum de G et μ(G) sa multiplicité (le nombre maximum d'arêtes par paire de sommets), alors :

Classification des graphes et détermination de leur nombre chromatique[modifier | modifier le code]

Comme énoncé ci-dessus, χ′(G) est toujours égal à Δ(G) ou à Δ(G) + 1. G est dit de classe 1 dans le premier cas et de classe 2 dans le second.

En 1981, Holyver a prouvé[1] 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) a établi[2] qu'un graphe simple planaire de degré maximum au moins égal à 8 est toujours de classe 1, et conjecturé qu'il en était de même pour un degré maximum égal à 6 ou 7 (on connaît des graphes simples planaires de degré maximum 2, 3, 4 ou 5 et de classe 2). Sanders (en) et Zhao[3] ont démontré le cas Δ(G) = 7 de sa conjecture.

Cette conjecture trouve une application dans celle de la coloration totale (en).

Notes et références[modifier | modifier le code]

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Edge coloring » (voir la liste des auteurs).

  1. (en) Ian Holyer, « The NP-completeness of edge-coloring », SIAM J. Comput., vol. 10, no 4,‎ , p. 718-720 (DOI 10.1137/0210055).
  2. (ru) V. G. Vizing, « Critical graphs with given chromatic class », Metody Diskret. Analiz., vol. 5, 1965, p. 9-17.
  3. (en) Daniel P. Sanders et Yue Zhao, « Planar graphs of maximum degree seven are class I », J. Combin. Theory Ser. B, vol. 83, no 2,‎ , p. 201-212 (DOI 10.1006/jctb.2001.2047).

Bibliographie[modifier | modifier le code]