List coloring

From Wikipedia, the free encyclopedia

In graph theory, a branch of mathematics, list coloring is a type of graph coloring.

More precisely, a list coloring is a choice function that maps every vertex to a color from a prescribed list for that vertex. A graph is k-choosable, or k-list-colorable, if it has a proper list coloring - one in which no two adjacent vertices receive the same color - for every collection of lists of k colors. The choosability, or list colorability, ch(G) of a graph G is the least number k such that G is k-choosable.

Some properties of ch(G) with n vertices:

1. ch(G) ≥ χ(G).
2. ch(G) is not bounded by chromatic number in general, that is, ch(G)≤ f(χ(G)) for some function f is not true in general.
3. ch(G) ≤ χ(G) ln(n).^{[citation needed]}
4. ch(G) ≤ Δ(G) + 1. (Vizing 1976; Erdős, Rubin, Taylor 1979)
5. ch(G) ≤ 5 if G is a planar graph. (Thomassen 1994)
6. ch(G) ≤ 3 if G is a bipartite, planar graph. (Alon, Tarsi 1992)

Here χ(G) is the chromatic number; and Δ(G), the maximum degree.

List coloring arises naturally out of practical optimization considerations.

[edit] See also

• List edge-coloring

[edit] References

• Alon, Noga; Tarsi, Michael (1992). Colorings and orientations of graphs. Combinatorica 12, 125–134.
• Erdős, P.; Rubin, A. L.; Taylor, H. (1979). Choosability in graphs. In Proc. West Coast Conference on Combinatorics, Graph Theory and Computing, Arcata, Congr. Num. 26, 125–157.
• Jensen, Tommy R.; Toft, Bjarne (1995). Graph coloring problems. New York: Wiley-Interscience. ISBN 0-471-02865-7.
• Thomassen, Carsten (1994). Every planar graph is 5-choosable. J. Combin. Theory (B) 64, 180–181.
• Vizing, V. G. (1976). Vertex colorings with given colors (in Russian). Metody Diskret. Analiz. 29, 3–10.