List Coloring - Example

Example

Let q be a positive integer, and let G be the complete bipartite graph K_q,qq. Let the available colors be represented by the q2 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 qq vertices be given sets of colors {0a, 1b, 2c, ...} in which the first digits are all distinct, for each of the qq possible choices of the q-tuple (a, b, c, ...). For instance, for q = 2, this construction produces the graph K_2,4. In this graph, the two vertices on one side of the bipartition have color sets {00,01} and {10,11} and the four vertices on the other side of the bipartition have color sets {00,10}, {00,11}, {01,10}, and {01,11}. 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.

Similarly, if, 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, for otherwise some vertex would remain uncolored, but this implies that some two adjacent vertices have the same color. In particular, the utility graph K_3,3 has chromatic index at least three, and the graph K_10,10 has chromatic index at least four.