List edge-coloring

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 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&prime;("G") < 2 χ&prime;("G").
# ch&prime;(K"n","n") = "n". (Galvin 1995)
# ch&prime;("G") < (1 + o(1))χ&prime;("G"), i.e. the list chromatic index and the chromatic index agree asymptotically. (Kahn 2000)Here χ&prime;("G") is the chromatic index of "G"; and K"n","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&prime;("G") = χ&prime;("G").

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 1995 using list edge-coloring.

See also

* List coloring
* Edge coloring

References

* Galvin, Fred (1995). The list chromatic index of a bipartite multigraph. "J. Combin. Theory (B)" 63, 153&ndash;158.
* Jensen, Tommy R.; Toft, Bjarne (1995). "Graph coloring problems". New York: Wiley-Interscience. ISBN 0-471-02865-7.
* Kahn, Jeff (2000). Asymptotics of the list chromatic index for multigraphs. "Rand. Struct. Alg." 17, 117&ndash;156.


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Edge coloring — A 3 edge coloring of the Desargues graph. 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… …   Wikipedia

  • List of graph theory topics — This is a list of graph theory topics, by Wikipedia page. See glossary of graph theory for basic terminology Contents 1 Examples and types of graphs 2 Graph coloring 3 Paths and cycles 4 …   Wikipedia

  • List coloring — In graph theory, a branch of mathematics, list coloring is a type of graph coloring where each vertex can be restricted to a list of allowed colors, first studied by Vizing [1] and by Erdős, Rubin, and Taylor.[2][3][4] …   Wikipedia

  • List of mathematics articles (L) — NOTOC L L (complexity) L BFGS L² cohomology L function L game L notation L system L theory L Analyse des Infiniment Petits pour l Intelligence des Lignes Courbes L Hôpital s rule L(R) La Géométrie Labeled graph Labelled enumeration theorem Lack… …   Wikipedia

  • List of terms relating to algorithms and data structures — The [http://www.nist.gov/dads/ NIST Dictionary of Algorithms and Data Structures] is a reference work maintained by the U.S. National Institute of Standards and Technology. It defines a large number of terms relating to algorithms and data… …   Wikipedia

  • List of mathematics articles (E) — NOTOC E E₇ E (mathematical constant) E function E₈ lattice E₈ manifold E∞ operad E7½ E8 investigation tool Earley parser Early stopping Earnshaw s theorem Earth mover s distance East Journal on Approximations Eastern Arabic numerals Easton s… …   Wikipedia

  • Graph coloring — A proper vertex coloring of the Petersen graph with 3 colors, the minimum number possible. 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… …   Wikipedia

  • List of unsolved problems in mathematics — This article lists some unsolved problems in mathematics. See individual articles for details and sources. Contents 1 Millennium Prize Problems 2 Other still unsolved problems 2.1 Additive number theory …   Wikipedia

  • List of algorithms — The following is a list of the algorithms described in Wikipedia. See also the list of data structures, list of algorithm general topics and list of terms relating to algorithms and data structures.If you intend to describe a new algorithm,… …   Wikipedia

  • List of marine aquarium fish species — The following list of marine aquarium fish species commonly available in the aquarium trade is not a completely comprehensive list; certain rare specimens may sometimes be available commercially yet not be listed here. A brief section on each,… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”