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]

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 k-choosable (or k-list-colorable) 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 k-choosable.

More generally, for a function f assigning a positive integer f(v) to each vertex v, a graph G is f-choosable (or f-list-colorable) 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, f-choosability corresponds to k-choosability.

Properties

Choosability ch(G) satisfies the following properties for a graph G with n vertices, chromatic number χ(G), and maximum degree Δ(G):

1. ch(G) ≥ χ(G). A k-list-colorable graph must in particular have a list coloring when every vertex is assigned the same list of k colors, which corresponds to a usual k-coloring.
2. 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.
3. ch(G) ≤ χ(G) ln(n).^[5][6]
4. ch(G) ≤ Δ(G) + 1.^[1][2]
5. ch(G) ≤ 5 if G is a planar graph.^[7]
6. 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:

1. k-choosability: decide whether a given graph is k-choosable for a given k, and
2. (j,k)-choosability: decide whether a given graph is f-choosable for a given function $f : V \to \{j,\dots,k\}$.

It is known that k-choosability in bipartite graphs is $\Pi^p_2$-complete for any k ≥ 3, and the same applies for 4-choosability in planar graphs, 3-choosability in planar triangle-free graphs, and (2,3)-choosability in bipartite planar graphs.^[3][9] For P₅-free graphs, that is, graphs excluding a 5-vertex path graph, k-choosability is fixed-parameter tractable. ^[10]

Applications

List coloring arises in practical problems concerning channel/frequency assignment.^{[citation needed]}

See also

• List edge-coloring

References

1. ^ ^{a b} Vizing, V. G. (1976), "Vertex colorings with given colors" (in Russian), Metody Diskret. Analiz. 29: 3–10 
2. ^ ^{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.math-inst.hu/~p_erdos/1980-07.pdf 
3. ^ ^{a b} Gutner, Shai (1996), "The complexity of planar graph choosability", Discrete Mathematics 159 (1): 119–130, arXiv:0802.2668, doi:10.1016/0012-365X(95)00104-5 .
4. ^ Jensen, Tommy R.; Toft, Bjarne (1995), Graph coloring problems, New York: Wiley-Interscience, ISBN 0-471-02865-7 
5. ^ 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 
6. ^ 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 
7. ^ Thomassen, Carsten (1994), "Every planar graph is 5-choosable", Journal of Combinatorial Theory, Series B 64: 180–181 
8. ^ Alon, Noga; Tarsi, Michael (1992), "Colorings and orientations of graphs", Combinatorica 12: 125–134, doi:10.1007/BF01204715 
9. ^ 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 
10. ^ Heggernes, Pinar; Golovach, Petr (2009), "Choosability of P₅-free graphs", Mathematical Foundations of Computer Science, Lecture Notes on Computer Science, 5734, Springer-Verlag, 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: Springer-Verlag, ISBN 978-3-642-00855-9 , Chapter 34 Five-coloring plane graphs.
• Diestel, Reinhard. Graph Theory. 3rd edition, Springer, 2005. Chapter 5.4 List Colouring. electronic edition available for download