List Coloring and List Chromatic Number

Coloring from Prescribed Lists

In an ordinary vertex-coloring problem, one chooses colors from a common palette. A list-coloring problem changes that constraint: each vertex comes with its own allowed set of colors. Even if every vertex has several available colors, adjacent vertices may have lists that fit together badly. Thus a graph can be easy to color ordinarily but impossible to color from a particular collection of lists.

Throughout, graphs are finite and simple, and colors are labels with no structure beyond whether two labels are equal. A proper coloring assigns a color to each vertex so that adjacent vertices receive different colors. The chromatic number \(\chi(G)\) is the smallest number of colors in a proper coloring of \(G\); for the graph with no vertices, set \(\chi(G)=0\).

The requirement is universal: to show that a graph is \(k\)-choosable, one must handle every permitted assignment, not just one convenient choice of lists. Conversely, a single assignment with lists of size at least \(k\) and no \(L\)-coloring proves that the graph is not \(k\)-choosable. Lists need not be equal, disjoint, or drawn from a palette of fixed size.

Ordinary Coloring and List Coloring

Ordinary coloring can be viewed as a special case in which every vertex receives the same list. But success with one common list does not establish success for all list assignments of that size. The difference is captured by a general comparison.

Proof. If \(G\) has no vertices, both parameters are \(0\), so the inequality holds. Suppose \(G\) is nonempty and let \(k=\chi_{\ell}(G)\). Give every vertex the same list consisting of \(k\) colors. Since \(G\) is \(k\)-choosable, this assignment has an \(L\)-coloring. That coloring is an ordinary proper coloring using at most \(k\) colors, so \(\chi(G)\le k=\chi_{\ell}(G)\). \(\square\)

The theorem gives a lower bound, but equality need not hold. List assignments can obstruct coloring in ways a common palette does not. The next example gives a bipartite graph with a 2-list assignment that has no coloring.

Subgraphs and Complete Graphs

List-colorability also behaves predictably when vertices or edges are removed. Here a subgraph \(H\) of \(G\) has \(V(H)\subseteq V(G)\) and \(E(H)\subseteq E(G)\), with each edge of \(H\) having both endpoints in \(V(H)\).

Proof. If \(G\) has no vertices, then \(H\) has no vertices and both list chromatic numbers are \(0\). Otherwise put \(k=\chi_{\ell}(G)\), which is at least \(1\). Consider any list assignment on \(H\) with lists of size at least \(k\). Extend it to \(G\) by giving each vertex in \(V(G)\setminus V(H)\) any \(k\)-element list. The extended assignment has lists of size at least \(k\), so \(G\), being \(k\)-choosable, has a coloring from those lists. Restrict that coloring to \(V(H)\). It remains proper on every edge of \(H\), and every vertex still receives a color from its original list. Thus every such assignment on \(H\) is colorable, so \(H\) is \(k\)-choosable and \(\chi_{\ell}(H)\le k=\chi_{\ell}(G)\). \(\square\)

This result is useful for lower bounds: finding a subgraph whose list chromatic number is large proves that the whole graph has list chromatic number at least as large. It also confirms that removing edges or vertices cannot increase the parameter. For instance, removing edges only removes coloring constraints, while removing vertices also removes the need to color those vertices.

Proof. If \(n=0\), the stated convention gives \(\chi_{\ell}(K_0)=0\). Suppose \(n\ge1\). For the upper bound, take any list assignment in which every list has at least \(n\) colors, and order the vertices \(v_1,\ldots,v_n\). Color them in this order. When \(v_i\) is reached, at most \(i-1\le n-1\) colors have been used on earlier vertices. Since \(v_i\)'s list has at least \(n\) colors, at least one color in that list has not been used on an earlier vertex. Assign such a color. Every pair of distinct vertices in \(K_n\) is adjacent, so this procedure gives a proper coloring. Hence \(K_n\) is \(n\)-choosable.

For the lower bound when \(n\ge2\), give every vertex the same list of \(n-1\) colors. A proper coloring of \(K_n\) must assign distinct colors to its \(n\) vertices, so \(n-1\) colors cannot suffice. Thus \(K_n\) is not \((n-1)\)-choosable. When \(n=1\), the empty list assignment on its sole vertex has no coloring, so \(K_1\) is not \(0\)-choosable. In each nonempty case, the upper and lower bounds give \(\chi_{\ell}(K_n)=n\). \(\square\)

Common Mistake and Practical Use

Common mistake: treating one successful palette as proof of list-colorability. For the graph in the first worked example, it is correct that the ordinary coloring \(u=\text{red}, v=\text{blue}\) uses two colors. But the incorrect calculation “there are two vertices, so give each one color from its list” overlooks that both lists are \(\{\text{red}\}\). The only list-respecting assignment gives both endpoints red, which violates the edge \(uv\). The correction is to check membership in every vertex's own list as well as the proper-coloring condition on every edge.

List coloring models situations in which different objects have different available choices: a vertex may represent a task or region, and its list may represent the colors permitted by local restrictions. The parameter \(\chi_{\ell}(G)\) asks for a uniform guarantee: how large must every vertex's list be to ensure a proper coloring, regardless of how the lists are chosen? It is therefore stronger than asking whether a particular graph can be colored from one fixed palette.

Keep three statements separate. An ordinary coloring uses colors from some palette; an \(L\)-coloring uses a color from each specified list; and \(k\)-choosability says that every assignment of lists of size at least \(k\) can be colored. In particular, one failed assignment disproves \(k\)-choosability, while one successful assignment does not prove it.