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. It was first studied in the 1970s in independent papers by Vizing and by Erdős, Rubin, and Taylor.^[1]

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.

Examples

Consider the complete bipartite graph G = K_2,4, having six vertices A, B, W, X, Y, Z such that A and B are each connected to all of W, X, Y, and Z, and no other vertices are connected. As a bipartite graph, G has usual chromatic number 2: one may color A and B in one color and W, X, Y, Z in another and no two adjacent vertices will have the same color. On the other hand, G has list-chromatic number larger than 2, as the following construction shows: assign to A and B the lists {red, blue} and {green, black}. Assign to the other four vertices the lists {red, green}, {red, black}, {blue, green}, and {blue, black}. No matter which choice one makes of a color from the list of A and a color from the list of B, there will be some other vertex such that both of its choices are already used to color its neighbors. Thus, G is not 2-choosable.

On the other hand, it is easy to see that G is 3-choosable: picking arbitrary colors for the vertices A and B leaves at least one available color for each of the remaining vertices, and these colors may be chosen arbitrarily.

A list coloring instance on the complete bipartite graph K_3,27 with three colors per vertex. No matter which colors are chosen for the three central vertices, one of the outer 27 vertices will be uncolorable, showing that the list chromatic number of K_3,27 is at least four.

More generally, let q be a positive integer, and let G be the complete bipartite graph K_q,q^q. Let the available colors be represented by the q² different two-digit numbers in radix q. On one side of the bipartition, let the q vertices be given sets of colors {i0, i1, i2, ...} in which the first digits are equal to each other, for each of the q possible choices of the first digit i. On the other side of the bipartition, let the q^q vertices be given sets of colors {0a, 1b, 2c, ...} in which the first digits are all distinct, for each of the q^q possible choices of the q-tuple (a, b, c, ...). The illustration shows a larger example of the same construction, with q = 3.

Then, G does not have a list coloring for L: no matter what set of colors is chosen for the vertices on the small side of the bipartition, this choice will conflict with all of the colors for one of the vertices on the other side of the bipartition. For instance if the vertex with color set {00,01} is colored 01, and the vertex with color set {10,11} is colored 10, then the vertex with color set {01,10} cannot be colored. Therefore, the list chromatic number of G is at least q + 1.^[2]

Similarly, if $n={\binom {2k-1}{k}}$ , then the complete bipartite graph K_{n, n} is not k-choosable. For, suppose that 2k − 1 colors are available in total, and that, on a single side of the bipartition, each vertex has available to it a different k-tuple of these colors than each other vertex. Then, each side of the bipartition must use at least k colors, because every set of k − 1 colors will be disjoint from the list of one vertex. Since at least k colors are used on one side and at least k are used on the other, there must be one color which is used on both sides, but this implies that two adjacent vertices have the same color. In particular, the utility graph K_3,3 has list-chromatic number at least three, and the graph K_10,10 has list-chromatic number at least four.^[3]

Properties

For a graph G, let χ(G) denote the chromatic number and Δ(G) the maximum degree of G. The list coloring number ch(G) satisfies the following properties.

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.
ch(G) cannot be bounded in terms of chromatic number in general, that is, there is no function f such that ch(G) ≤ f(χ(G)) holds for every graph G. In particular, as the complete bipartite graph examples show, there exist graphs with χ(G) = 2 but with ch(G) arbitrarily large.^[2]
ch(G) ≤ χ(G) ln(n) where n is the number of vertices of G.^[4]^[5]
ch(G) ≤ Δ(G) + 1.^[3]^[6]
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:

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

It is known that k-choosability in bipartite graphs is $\Pi _{2}^{p}$ -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.^[9]^[10] For P₅-free graphs, that is, graphs excluding a 5-vertex path graph, k-choosability is fixed-parameter tractable. ^[11]

It is possible to test whether a graph is 2-choosable in linear time by repeatedly deleting vertices of degree zero or one until reaching the 2-core of the graph, after which no more such deletions are possible. The initial graph is 2-choosable if and only if its 2-core is either an even cycle or a theta graph formed by three paths with shared endpoints, with two paths of length two and the third path having any even length.^[3]

Applications

List coloring arises in practical problems concerning channel/frequency assignment.^[12]^[13]

References

^ Jensen, Tommy R.; Toft, Bjarne (1995), "1.9 List coloring", Graph coloring problems, New York: Wiley-Interscience, pp. 18–21, ISBN 0-471-02865-7
^ ^a ^b Gravier, Sylvain (1996), "A Hajós-like theorem for list coloring", Discrete Mathematics, 152 (1–3): 299–302, doi:10.1016/0012-365X(95)00350-6, MR 1388650.
^ ^a ^b ^c Erdős, P.; Rubin, A. L.; Taylor, H. (1979), "Choosability in graphs", Proc. West Coast Conference on Combinatorics, Graph Theory and Computing, Arcata (PDF), Congressus Numerantium, vol. 26, pp. 125–157, archived from the original (PDF) on 2016-03-09, retrieved 2008-11-10
^ Eaton, Nancy (2003), "On two short proofs about list coloring - Part 1" (PDF), Talk, archived from the original (PDF) on August 29, 2017, retrieved May 29, 2010
^ Eaton, Nancy (2003), "On two short proofs about list coloring - Part 2" (PDF), Talk, archived from the original (PDF) on August 30, 2017, retrieved May 29, 2010
^ Vizing, V. G. (1976), "Vertex colorings with given colors", Metody Diskret. Analiz. (in Russian), 29: 3–10
^ Thomassen, Carsten (1994), "Every planar graph is 5-choosable", Journal of Combinatorial Theory, Series B, 62: 180–181, doi:10.1006/jctb.1994.1062
^ Alon, Noga; Tarsi, Michael (1992), "Colorings and orientations of graphs", Combinatorica, 12 (2): 125–134, CiteSeerX 10.1.1.106.9928, doi:10.1007/BF01204715, S2CID 45528500
^ 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, S2CID 1392057.
^ 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₅-free graphs" (PDF), Mathematical Foundations of Computer Science, Lecture Notes on Computer Science, vol. 5734, Springer-Verlag, pp. 382–391
^ Wang, Wei; Liu, Xin (2005), "List-coloring based channel allocation for open-spectrum wireless networks", 2005 IEEE 62nd Vehicular Technology Conference (VTC 2005-Fall), vol. 1, pp. 690–694, doi:10.1109/VETECF.2005.1558001, ISBN 0-7803-9152-7, S2CID 14952297.
^ Garg, N.; Papatriantafilou, M.; Tsigas, P. (1996), "Distributed list coloring: how to dynamically allocate frequencies to mobile base stations", Eighth IEEE Symposium on Parallel and Distributed Processing, pp. 18–25, doi:10.1109/SPDP.1996.570312, hdl:21.11116/0000-0001-1AE6-F, ISBN 0-8186-7683-3, S2CID 3319306.

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

[1] Jensen, Tommy R.; Toft, Bjarne (1995), "1.9 List coloring", Graph coloring problems, New York: Wiley-Interscience, pp. 18–21, ISBN 0-471-02865-7

[g96-2] Gravier, Sylvain (1996), "A Hajós-like theorem for list coloring", Discrete Mathematics, 152 (1–3): 299–302, doi:10.1016/0012-365X(95)00350-6, MR 1388650.

[erdos-3] Erdős, P.; Rubin, A. L.; Taylor, H. (1979), "Choosability in graphs", Proc. West Coast Conference on Combinatorics, Graph Theory and Computing, Arcata (PDF), Congressus Numerantium, vol. 26, pp. 125–157, archived from the original (PDF) on 2016-03-09, retrieved 2008-11-10

[4] Eaton, Nancy (2003), "On two short proofs about list coloring - Part 1" (PDF), Talk, archived from the original (PDF) on August 29, 2017, retrieved May 29, 2010

[5] Eaton, Nancy (2003), "On two short proofs about list coloring - Part 2" (PDF), Talk, archived from the original (PDF) on August 30, 2017, retrieved May 29, 2010

[vizing-6] Vizing, V. G. (1976), "Vertex colorings with given colors", Metody Diskret. Analiz. (in Russian), 29: 3–10

[thomassen-7] Thomassen, Carsten (1994), "Every planar graph is 5-choosable", Journal of Combinatorial Theory, Series B, 62: 180–181, doi:10.1006/jctb.1994.1062

[alon-8] Alon, Noga; Tarsi, Michael (1992), "Colorings and orientations of graphs", Combinatorica, 12 (2): 125–134, CiteSeerX 10.1.1.106.9928, doi:10.1007/BF01204715, S2CID 45528500

[gutner-9] 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, S2CID 1392057.

[GutnerTarsi-10] 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

[11] Heggernes, Pinar; Golovach, Petr (2009), "Choosability of P₅-free graphs" (PDF), Mathematical Foundations of Computer Science, Lecture Notes on Computer Science, vol. 5734, Springer-Verlag, pp. 382–391

[12] Wang, Wei; Liu, Xin (2005), "List-coloring based channel allocation for open-spectrum wireless networks", 2005 IEEE 62nd Vehicular Technology Conference (VTC 2005-Fall), vol. 1, pp. 690–694, doi:10.1109/VETECF.2005.1558001, ISBN 0-7803-9152-7, S2CID 14952297.

[13] Garg, N.; Papatriantafilou, M.; Tsigas, P. (1996), "Distributed list coloring: how to dynamically allocate frequencies to mobile base stations", Eighth IEEE Symposium on Parallel and Distributed Processing, pp. 18–25, doi:10.1109/SPDP.1996.570312, hdl:21.11116/0000-0001-1AE6-F, ISBN 0-8186-7683-3, S2CID 3319306.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]