List coloring

It was first studied in the 1970s in independent papers by Vizing and by Erdős, Rubin, and Taylor.

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.

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}.

More generally, let q be a positive integer, and let G be the complete bipartite graph Kq,qq.

Let the available colors be represented by the q2 different two-digit numbers in radix q.

[3] 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.

Two algorithmic problems have been considered in the literature: It is known that k-choosability in bipartite graphs is

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

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.