List edge-coloring
Encyclopedia
In mathematics
, list edge-coloring is a type of graph coloring
.
More precisely, a list edge-coloring is a choice function that maps every edge to a color from a prescribed list for that edge.
A graph is k-edge-choosable if it has a proper list edge-coloring - one in which no two adjacent edges receive the same color - for every collection of lists of k colors.
The edge choosability, or list edge colorability, list edge chromatic number, or list chromatic index, ch′(G) of a graph G is the least number k such that G is k-edge-choosable.
Some properties of ch′(G):
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.
List coloring conjecture.
This conjecture has a fuzzy origin.
Interested readers are directed to[Jensen, Toft 1995] for an overview of its history.
It is also a generalization of the longstanding Dinitz conjecture
, which was eventually solved by Galvin in 1994 using list edge-coloring.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, list edge-coloring is a type of graph coloring
Graph coloring
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the...
.
More precisely, a list edge-coloring is a choice function that maps every edge to a color from a prescribed list for that edge.
A graph is k-edge-choosable if it has a proper list edge-coloring - one in which no two adjacent edges receive the same color - for every collection of lists of k colors.
The edge choosability, or list edge colorability, list edge chromatic number, or list chromatic index, ch′(G) of a graph G is the least number k such that G is k-edge-choosable.
Some properties of ch′(G):
- ch′(G) < 2 χ′(G).
- ch′(Kn,n) = n. (Galvin 1995)
- ch′(G) < (1 + o(1))χ′(G), i.e. the list chromatic index and the chromatic index agree asymptotically. (Kahn 2000)
Here χ′(G) is the chromatic index
Edge coloring
In graph theory, an edge coloring of a graph is an assignment of “colors” to the edges of the graph so that no two adjacent edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several...
of G; and Kn,n, the complete bipartite graph
Complete bipartite graph
In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set.- Definition :...
with equal partite sets
Glossary of graph theory
Graph theory is a growing area in mathematical research, and has a large specialized vocabulary. Some authors use the same word with different meanings. Some authors use different words to mean the same thing. This page attempts to keep up with current usage....
.
The most famous open problem about list edge-coloring is probably the list coloring conjecture.
List coloring conjecture.
- ch′(G) = χ′(G).
This conjecture has a fuzzy origin.
Interested readers are directed to
It is also a generalization of the longstanding Dinitz conjecture
Dinitz conjecture
In combinatorics, the Dinitz conjecture is a statement about the extension of arrays to partial Latin squares, proposed in 1979 by Jeff Dinitz, and proved in 1994 by Fred Galvin....
, which was eventually solved by Galvin in 1994 using list edge-coloring.