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 Vizingand by Erdős, Rubin, and Taylor.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.Consider the complete bipartite graph G = K2,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.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:List coloring arises in practical problems concerning channel/frequency assignment.Further reading