Degeneracy Bounds for List Coloring

Degeneracy as an Ordering Condition

List coloring asks for more than an ordinary coloring: each vertex has its own permitted set of colors, and the color assigned to that vertex must come from that set. A useful way to guarantee a coloring is to order the vertices so that each one has only a few neighbors still to be considered. The direction of coloring then matters: color in reverse order, so each vertex has few neighbors whose colors have already been chosen.

Throughout, graphs are finite and simple. A subgraph is formed by taking some vertices and some of the edges between them. A list assignment \(L\) gives each vertex \(v\) a finite set \(L(v)\) of available colors. A proper list coloring is a choice of a color \(c(v)\in L(v)\) for every vertex such that \(c(u)\ne c(v)\) whenever \(uv\) is an edge.

The ordering condition expresses the same restriction as the subgraph definition. To build such an ordering, repeatedly remove a vertex of degree at most \(d\) from the graph that remains. Record the vertices in removal order. Conversely, from a valid ordering, any nonempty subgraph contains a vertex with the smallest index among its vertices; all its neighbors in that subgraph have larger indices, so there are at most \(d\) of them.

Proof. Suppose first that \(G\) is \(d\)-degenerate. If \(G\) is empty, its empty ordering has the required property. Otherwise, choose a vertex \(v_1\) of degree at most \(d\) in \(G\), which exists by the definition. Remove it. If vertices remain, the remaining graph is a nonempty subgraph of \(G\), so it has a vertex \(v_2\) of degree at most \(d\). Continue in this way until no vertices remain. When \(v_i\) was removed, its neighbors still present were precisely its neighbors later in the recorded ordering. Thus it has at most \(d\) later neighbors, as required.

Conversely, suppose \(v_1,\ldots,v_n\) is a \(d\)-degeneracy ordering, and let \(H\) be any nonempty subgraph of \(G\). Choose the vertex \(v_i\) of \(H\) with the smallest index. Every neighbor of \(v_i\) in \(H\) has a larger index, since no vertex of \(H\) has a smaller index. The ordering condition gives at most \(d\) such neighbors in \(G\), and hence at most \(d\) in \(H\). Therefore \(H\) has a vertex of degree at most \(d\). This holds for every nonempty subgraph, so \(G\) is \(d\)-degenerate. \(\square\)

The List-Coloring Bound

Proof. For the empty graph, the empty assignment is a proper list coloring. Otherwise, take a \(d\)-degeneracy ordering \(v_1,\ldots,v_n\), whose existence follows from the characterization just proved. Color the vertices in the order \(v_n,v_{n-1},\ldots,v_1\). When coloring \(v_i\), only its neighbors with larger indices have already been colored. There are at most \(d\) such neighbors, so their colors can exclude at most \(d\) colors from \(L(v_i)\). Since \(|L(v_i)|\ge d+1\), at least one color in \(L(v_i)\) remains available. Choose one of those colors.

To check that the final coloring is proper, consider any edge \(v_iv_j\), where \(i<j\). The vertex \(v_j\) was colored before \(v_i\), and its color was therefore excluded when \(v_i\) was colored. The endpoints receive different colors. This applies to every edge, proving the coloring is proper. \(\square\)

The bound is guaranteed for arbitrary lists, even when lists at adjacent vertices differ. It depends on the number of later neighbors in a suitable ordering, not on the maximum degree. In particular, a vertex may have many neighbors in the original graph but still be colored after most of them have been removed from consideration.

Why the Bound Is Best Possible

The list size \(d+1\) cannot be replaced by \(d\) as a guarantee for every \(d\)-degenerate graph. For any integer \(d\ge0\), the complete graph \(K_{d+1}\) is \(d\)-degenerate: a nonempty subgraph with \(k\) vertices has every degree at most \(k-1\le d\). Give each vertex the same list of \(d\) colors. A proper coloring of \(K_{d+1}\) needs \(d+1\) distinct colors, because every pair of its vertices is adjacent, but only \(d\) colors are available.

For \(d=0\), this example is \(K_1\) with an empty list: its single vertex cannot be assigned a color. Thus the failure also holds in the boundary case. This example shows that the theorem is a universal guarantee about list sizes; a particular graph or particular assignment may still be colorable from smaller lists.

Common Pitfall: Coloring in the Wrong Direction

A degeneracy ordering bounds the number of neighbors later in that ordering. It does not bound the number of already-colored neighbors if the ordering is used forward. For a concrete failure, let \(G\) be the star with \(V=\{x_1,x_2,x_3,c\}\) and \(E=\{x_1c,x_2c,x_3c\}\). It is \(1\)-degenerate: the ordering \(x_1,x_2,x_3,c\) has later-neighbor counts \(1,1,1,0\).

Give all four vertices the list \(\{\text{red},\text{blue}\}\). If one incorrectly colors forward in that ordering, one possible sequence is \(x_1=\text{red}\), \(x_2=\text{blue}\), \(x_3=\text{red}\). At \(c\), both colors are forbidden by its three colored neighbors, so this procedure gets stuck. The failure does not contradict the theorem; the procedure used the wrong direction.

In the required reverse order \(c,x_3,x_2,x_1\), choose red for \(c\). Each leaf is adjacent only to \(c\), so each can be assigned blue. All lists contain the chosen colors, and every edge joins a red center to a blue leaf. The key check is therefore not simply that an ordering exists, but that vertices are colored in reverse of the order that bounds their later neighbors.