Misplaced Pages

List edge-coloring

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
Graph edge coloring with a limited number of allowed colors

In graph theory, 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.

Properties

Some properties of ch'(G):

  1. ch ′ ⁡ ( G ) < 2 χ ′ ( G ) . {\displaystyle \operatorname {ch} '(G)<2\chi '(G).}
  2. ch ′ ⁡ ( K n , n ) = n . {\displaystyle \operatorname {ch} '(K_{n,n})=n.} This is the Dinitz conjecture, proven by Galvin (1995).
  3. ch ′ ⁡ ( G ) < ( 1 + o ( 1 ) ) χ ′ ( G ) , {\displaystyle \operatorname {ch} '(G)<(1+o(1))\chi '(G),} i.e. the list chromatic index and the chromatic index agree asymptotically (Kahn 2000).

Here χ′(G) is the chromatic index of G; and Kn,n, the complete bipartite graph with equal partite sets.

List coloring conjecture

The most famous open problem about list edge-coloring is probably the list coloring conjecture.

ch ′ ⁡ ( G ) = χ ′ ( G ) . {\displaystyle \operatorname {ch} '(G)=\chi '(G).}

This conjecture has a fuzzy origin; Jensen & Toft (1995) overview its history. The Dinitz conjecture, proven by Galvin (1995), is the special case of the list coloring conjecture for the complete bipartite graphs Kn,n.

References

Category: