 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]}
Contents
Definition
Given a graph G and given a set L(v) of colors for each vertex v (called a list), a list coloring is a choice function that maps every vertex v to a color in the list L(v). As with graph coloring, a list coloring is generally assumed to be proper, meaning no two adjacent vertices receive the same color. A graph is kchoosable (or klistcolorable) if it has a proper list coloring no matter how one assigns a list of k colors to each vertex. The choosability (or list colorability or list chromatic number) ch(G) of a graph G is the least number k such that G is kchoosable.
More generally, for a function f assigning a positive integer f(v) to each vertex v, a graph G is fchoosable (or flistcolorable) if it has a list coloring no matter how one assigns a list of f(v) colors to each vertex v. In particular, if f(v) = k for all vertices v, fchoosability corresponds to kchoosability.
Properties
Choosability ch(G) satisfies the following properties for a graph G with n vertices, chromatic number χ(G), and maximum degree Δ(G):
 ch(G) ≥ χ(G). A klistcolorable graph must in particular have a list coloring when every vertex is assigned the same list of k colors, which corresponds to a usual kcoloring.
 ch(G) cannot be bounded in terms of chromatic number in general, that is, ch(G) ≤ f(χ(G)) does not hold in general for any function f.
 ch(G) ≤ χ(G) ln(n).^{[5]}^{[6]}
 ch(G) ≤ Δ(G) + 1.^{[1]}^{[2]}
 ch(G) ≤ 5 if G is a planar graph.^{[7]}
 ch(G) ≤ 3 if G is a bipartite planar graph.^{[8]}
Computing choosability and (a,b)choosability
Two algorithmic problems have been considered in the literature:
 kchoosability: decide whether a given graph is kchoosable for a given k, and
 (j,k)choosability: decide whether a given graph is fchoosable for a given function .
It is known that kchoosability in bipartite graphs is complete for any k ≥ 3, and the same applies for 4choosability in planar graphs, 3choosability in planar trianglefree graphs, and (2,3)choosability in bipartite planar graphs.^{[3]}^{[9]} For P_{5}free graphs, that is, graphs excluding a 5vertex path graph, kchoosability is fixedparameter tractable. ^{[10]}
Applications
List coloring arises in practical problems concerning channel/frequency assignment.^{[citation needed]}
See also
References
 ^ ^{a} ^{b} Vizing, V. G. (1976), "Vertex colorings with given colors" (in Russian), Metody Diskret. Analiz. 29: 3–10
 ^ ^{a} ^{b} Erdős, P.; Rubin, A. L.; Taylor, H. (1979), "Choosability in graphs", Proc. West Coast Conference on Combinatorics, Graph Theory and Computing, Arcata, Congressus Numerantium, 26, pp. 125–157, http://www.mathinst.hu/~p_erdos/198007.pdf
 ^ ^{a} ^{b} Gutner, Shai (1996), "The complexity of planar graph choosability", Discrete Mathematics 159 (1): 119–130, arXiv:0802.2668, doi:10.1016/0012365X(95)001045.
 ^ Jensen, Tommy R.; Toft, Bjarne (1995), Graph coloring problems, New York: WileyInterscience, ISBN 0471028657
 ^ Eaton, Nancy (2003), "On two short proofs about list coloring  Part 1", Talk, http://www.math.uri.edu/~eaton/TalkUriOct03P1.pdf, retrieved May 29, 2010
 ^ Eaton, Nancy (2003), "On two short proofs about list coloring  Part 2", Talk, http://www.math.uri.edu/~eaton/TalkUriOct03P2.pdf, retrieved May 29, 2010
 ^ Thomassen, Carsten (1994), "Every planar graph is 5choosable", Journal of Combinatorial Theory, Series B 64: 180–181
 ^ Alon, Noga; Tarsi, Michael (1992), "Colorings and orientations of graphs", Combinatorica 12: 125–134, doi:10.1007/BF01204715
 ^ Gutner, Shai; Tarsi, Michael (2009), "Some results on (a:b)choosability", Discrete Mathematics 309 (8): 2260–2270, doi:10.1016/j.disc.2008.04.061
 ^ Heggernes, Pinar; Golovach, Petr (2009), "Choosability of P_{5}free graphs", Mathematical Foundations of Computer Science, Lecture Notes on Computer Science, 5734, SpringerVerlag, pp. 382–391, http://www.ii.uib.no/~pinar/Choosability.pdf
Further reading
 Aigner, Martin; Ziegler, Günter (2009), Proofs from THE BOOK (4th ed.), Berlin, New York: SpringerVerlag, ISBN 9783642008559, Chapter 34 Fivecoloring plane graphs.
 Diestel, Reinhard. Graph Theory. 3rd edition, Springer, 2005. Chapter 5.4 List Colouring. electronic edition available for download
Categories:
Wikimedia Foundation. 2010.