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.

Definition

Given a graph Template:Mvar and given a set Template:Math of colors for each vertex Template:Mvar (called a list), a list coloring is a choice function that maps every vertex Template:Mvar to a color in the list Template:Math. 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 Template:Mvar-choosable (or Template:Mvar-list-colorable) if it has a proper list coloring no matter how one assigns a list of Template:Mvar colors to each vertex. The choosability (or list colorability or list chromatic number) Template:Math of a graph Template:Mvar is the least number Template:Mvar such that Template:Mvar is Template:Mvar-choosable.

More generally, for a function Template:Mvar assigning a positive integer Template:Math to each vertex Template:Mvar, a graph Template:Mvar is Template:Mvar-choosable (or Template:Mvar-list-colorable) if it has a list coloring no matter how one assigns a list of Template:Math colors to each vertex Template:Mvar. In particular, if Template:Math for all vertices Template:Mvar, Template:Mvar-choosability corresponds to Template:Mvar-choosability.

Examples

Consider the complete bipartite graph Template:Math, having six vertices Template:Mvar, Template:Mvar, Template:Mvar, Template:Mvar, Template:Mvar, Template:Mvar such that Template:Mvar and Template:Mvar are each connected to all of Template:Mvar, Template:Mvar, Template:Mvar, and Template:Mvar, and no other vertices are connected. As a bipartite graph, Template:Mvar has usual chromatic number 2: one may color Template:Mvar and Template:Mvar in one color and Template:Mvar, Template:Mvar, Template:Mvar, Template:Mvar in another and no two adjacent vertices will have the same color. On the other hand, Template:Mvar has list-chromatic number larger than 2, as the following construction shows: assign to Template:Mvar and Template:Mvar 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 Template:Mvar and a color from the list of Template:Mvar, there will be some other vertex such that both of its choices are already used to color its neighbors. Thus, Template:Mvar is not 2-choosable.

On the other hand, it is easy to see that Template:Mvar is 3-choosable: picking arbitrary colors for the vertices Template:Mvar and Template:Mvar 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 Template:Math 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 Template:Math is at least four.

More generally, let Template:Mvar be a positive integer, and let Template:Mvar be the complete bipartite graph Template:Mvar. Let the available colors be represented by the Template:Math different two-digit numbers in radix Template:Mvar. On one side of the bipartition, let the Template:Mvar vertices be given sets of colors Template:Math} in which the first digits are equal to each other, for each of the Template:Mvar possible choices of the first digit Template:Mvar. On the other side of the bipartition, let the Template:Mvar vertices be given sets of colors Template:Math} in which the first digits are all distinct, for each of the Template:Mvar possible choices of the Template:Mvar-tuple Template:Math The illustration shows a larger example of the same construction, with Template:Math.

Then, Template:Mvar does not have a list coloring for Template:Mvar: 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 Template:Mvar is at least Template:Math.

Similarly, if $n=(\genfrac{}{}{0ex}{}{2k-1}{k}),$ then the complete bipartite graph Template:Mvar is not Template:Mvar-choosable. For, suppose that Template:Math colors are available in total, and that, on a single side of the bipartition, each vertex has available to it a different Template:Mvar-tuple of these colors than each other vertex. Then, each side of the bipartition must use at least Template:Mvar colors, because every set of Template:Math colors will be disjoint from the list of one vertex. Since at least Template:Mvar colors are used on one side and at least Template:Mvar 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 Template:Math has list-chromatic number at least three, and the graph Template:Math has list-chromatic number at least four.

Properties

For a graph Template:Mvar, let Template:Math denote the chromatic number and Template:Math the maximum degree of Template:Mvar. The list coloring number Template:Math satisfies the following properties.

1. Template:Math. A Template:Mvar-list-colorable graph must in particular have a list coloring when every vertex is assigned the same list of Template:Mvar colors, which corresponds to a usual Template:Mvar-coloring.
2. Template:Math cannot be bounded in terms of chromatic number in general, that is, there is no function Template:Mvar such that Template:Math holds for every graph Template:Mvar. In particular, as the complete bipartite graph examples show, there exist graphs with Template:Math but with Template:Math arbitrarily large.
3. Template:Math where Template:Mvar is the number of vertices of Template:Mvar.
4. Template:Math.
5. Template:Math if Template:Mvar is a planar graph.
6. Template:Math if Template:Mvar is a bipartite planar graph.

Computing choosability and (a, b)-choosability

Two algorithmic problems have been considered in the literature:

1. Template:Mvar-choosability: decide whether a given graph is Template:Mvar-choosable for a given Template:Mvar, and
2. Template:Math-choosability: decide whether a given graph is Template:Mvar-choosable for a given function $f:V\to \{a,\dots ,b\}$.

It is known that Template:Mvar-choosability in bipartite graphs is ${\mathrm{\Pi }}_2^p$-complete for any Template:Math, 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. For Template:Math-free graphs, that is, graphs excluding a 5-vertex path graph, Template:Mvar-choosability is fixed-parameter tractable.

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.

Applications

List coloring arises in practical problems concerning channel/frequency assignment.

See also

• List edge-coloring

References

Further reading

• Template:Citation, Chapter 34 Five-coloring plane graphs.
• Diestel, Reinhard. Graph Theory. 3rd edition, Springer, 2005. Chapter 5.4 List Colouring. electronic edition available for download