Ê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
List edge-coloring
Résumé
In mathematics, list edge-coloring is a type of graph coloring that combines list coloring and edge coloring.
An instance of a list edge-coloring problem consists of a graph together with a list of allowed colors for each edge. A list edge-coloring is a choice of a color for each edge, from its list of allowed colors; a coloring is proper if no two adjacent edges receive the same color.
A graph G is k-edge-choosable if every instance of list edge-coloring that has G as its underlying graph and that provides at least k allowed colors for each edge of G has a proper coloring.
The edge choosability, or list edge colorability, list edge chromatic number, or list chromatic index, ch(G) of graph G is the least number k such that G is k-edge-choosable. It is conjectured that it always equals the chromatic index.
Some properties of ch(G):
ch(G) < 2 χ(G).
ch(Kn,n) = n. This is the Dinitz conjecture, proven by .
ch(G) < (1 + o(1))χ(G), i.e. the list chromatic index and the chromatic index agree asymptotically .
Here χ(G) is the chromatic index of G; and Kn,n, the complete bipartite graph with equal partite sets.
The most famous open problem about list edge-coloring is probably the list coloring conjecture.
ch(G) = χ(G).
This conjecture has a fuzzy origin; overview its history. The Dinitz conjecture, proven by , is the special case of the list coloring conjecture for the complete bipartite graphs Kn,n.
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.