FACTOID # 19: Cheap sloppy joes: Looking for reduced-price lunches for schoolchildren? Head for Oklahoma!

 Home Encyclopedia Statistics States A-Z Flags Maps FAQ About

 WHAT'S NEW

SEARCH ALL

Search encyclopedia, statistics and forums:

(* = Graphable)

Encyclopedia > List edge coloring

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 an list edge-coloring 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):

1. ch′(G) < 2 χ′(G).
2. ch′(Kn,n) = n. (Galvin 1995)

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.

ch′(G) = χ′(G).

This conjecture has a fuzzy origin. Interested readers are directed to [Jensen, Toft 1995] for an overview of its history. This conjecture is a generalization of the longstanding Dinitz conjecture, which was eventually solved by Galvin in 1995 using list edge-coloring.

References

• Galvin, Fred (1995). The list chromatic index of a bipartitle multigraph. J. Combin. Theory (B) 63, 153–158.
• Jensen, Tommy R.; Toft, Bjarne (1995). Graph coloring problems. New York: Wiley-Interscience. ISBN 0-471-02865-7.

Results from FactBites:

 Total coloring - Wikipedia, the free encyclopedia (353 words) In graph theory, total coloring is a type of coloring on the vertices and edges of a graph. Total coloring arises naturally since it is simply a mix of vertex and edge colorings. Apparently, the term "total coloring" and the statement of total coloring conjecture were independently introduced by Behzad and Vizing in numerous occasions between 1964 and 1968.
 Edge - encyclopedia article about Edge. (2064 words) Edge is a colloquial adjective to describe escarpments In geology, an escarpment is a transition zone between different physiogeographic provinces that involves an elevation differential, often involving high cliffs. Edge Hill Edge Hill is an escarpment and hamlet in the county of Warwickshire, England (national grid reference SP3747). Edge is also the stage name of Canadian Canada is a country in northern North America bordered on the south by the United States and extending through the Arctic Ocean to the North Pole, making it the northernmost country in the world.
More results at FactBites »

Share your thoughts, questions and commentary here