Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Coloration des arêtes d'un graphe
Résumé
thumb|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.
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 χ(G). Il ne doit pas être confondu avec le nombre chromatique (des sommets) de G, noté χ(G).
Si Δ(G) est le degré maximum de G et μ(G) sa multiplicité (le nombre maximum d'arêtes par paire de sommets), alors :
χ′(G) = 1 si et seulement si G est un couplage.
χ′(G) ≥ Δ(G).
χ′(G) ≤ Δ(G) + 1 (théorème de Vizing).
χ′(G) ≤ Δ(G) + μ(G), où G peut être un multigraphe.
χ′(G) = Δ(G) dès que G est un graphe biparti (théorème de Kőnig sur les graphes bipartis).
χ′(G) = Δ(G) dès que G est un graphe simple planaire tel que Δ(G) ≥ 7 ( section suivante).
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, Holyer 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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Proximité ontologique