List coloring
|
|
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 list coloring 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:
- ch(G) ≥ χ(G).
- 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.
- ch(G) ≤ χ(G) ln(n).
- ch(G) ≤ Δ(G) + 1. (Vizing 1976; Erdős, Rubin, Taylor 1979)
- ch(G) ≤ 5 if G is a planar graph. (Thomassen 1994)
- 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.
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.