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 and given a set of colors for each vertex (called a list), a list coloring is a choice function that maps every vertex to a color in the list . 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 -choosable (or -list-colorable) if it has a proper list coloring no matter how one assigns a list of colors to each vertex. The choosability (or list colorability or list chromatic number) of a graph is the least number such that is -choosable.
More generally, for a function assigning a positive integer to each vertex, a graph is -choosable (or -list-colorable) if it has a list coloring no matter how one assigns a list of colors to each vertex . In particular, if for all vertices, -choosability corresponds to -choosability.
Consider the complete bipartite graph, having six vertices,,,,, such that and are each connected to all of,,, and, and no other vertices are connected. As a bipartite graph, has usual chromatic number 2: one may color and in one color and,,, in another and no two adjacent vertices will have the same color. On the other hand, has list-chromatic number larger than 2, as the following construction shows: assign to and the lists and . Assign to the other four vertices the lists,,, and . No matter which choice one makes of a color from the list of and a color from the list of, there will be some other vertex such that both of its choices are already used to color its neighbors. Thus, is not 2-choosable.
On the other hand, it is easy to see that is 3-choosable: picking arbitrary colors for the vertices and leaves at least one available color for each of the remaining vertices, and these colors may be chosen arbitrarily.
More generally, let be a positive integer, and let be the complete bipartite graph . Let the available colors be represented by the different two-digit numbers in radix .On one side of the bipartition, let the vertices be given sets of colors in which the first digits are equal to each other, for each of the possible choices of the first digit .On the other side of the bipartition, let the vertices be given sets of colors in which the first digits are all distinct, for each of the possible choices of the -tuple The illustration shows a larger example of the same construction, with .
Then, does not have a list coloring for : 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 is colored 01, and the vertex with color set is colored 10, then the vertex with color set cannot be colored.Therefore, the list chromatic number of is at least .[1]
Similarly, if
n=\tbinom{2k-1}{k},
For a graph, let denote the chromatic number and the maximum degree of . The list coloring number satisfies the following properties.
Two algorithmic problems have been considered in the literature:
f:V\to\{a,...,b\}
| p | |
| \Pi | |
| 2 |
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.
List coloring arises in practical problems concerning channel/frequency assignment.[3] [4]
Further reading