List Coloring Chordal Graphs

List Coloring and the Chordal-Graph Bound

In an ordinary coloring, a color may be chosen from a common palette. In a list coloring, each vertex has its own permitted set of colors, and the choices must respect both the lists and the graph’s edges. For chordal graphs, a perfect elimination ordering provides a direct way to make those choices: color vertices in reverse order, so that the neighbors already colored at each step form a clique. The size of that clique gives the bound on how many colors can be unavailable.

All graphs below are finite and simple. A proper coloring assigns a color to each vertex so that adjacent vertices receive different colors. A list assignment \(L\) assigns a finite set \(L(v)\) of permitted colors to each vertex \(v\). A proper coloring \(c\) is an \(L\)-coloring if \(c(v)\in L(v)\) for every vertex. Lists need not be equal, and colors in lists are not required to have any particular names or ordering.

A clique is a set of pairwise adjacent vertices. For a nonempty graph \(G\), its clique number \(\omega(G)\) is the largest size of a clique in \(G\). We use the standard characterization of chordal graphs by perfect elimination orderings: a finite graph is chordal if and only if it has a PEO. This characterization was established in the earlier material on chordal graphs; here the coloring argument uses the ordering in the direction that matters for lists.

Why the Reverse Order Works

Suppose \(v_1,\ldots,v_n\) is a PEO, and color \(v_n,v_{n-1},\ldots,v_1\), in that order. When it is time to color \(v_i\), the vertices already colored are exactly the vertices \(v_j\) with \(j>i\). Consequently, the already-colored neighbors of \(v_i\) are precisely its later neighbors in the PEO. Those neighbors form a clique. Together with \(v_i\), they form a clique as well, so \(v_i\) has at most \(\omega(G)-1\) already-colored neighbors.

Proof. Since \(G\) is chordal, choose a PEO \(v_1,\ldots,v_n\). We color in the order \(v_n,v_{n-1},\ldots,v_1\). Assume that the vertices \(v_{i+1},\ldots,v_n\) have already been colored properly. The already-colored neighbors of \(v_i\) are its later neighbors. By the PEO property, these neighbors form a clique; adding \(v_i\) gives a clique in \(G\). Therefore there are at most \(\omega(G)-1\) such neighbors. At most \(\omega(G)-1\) distinct colors can appear on them, so at most \(\omega(G)-1\) colors in \(L(v_i)\) are forbidden. Since \(|L(v_i)|\geq\omega(G)\), at least one color in \(L(v_i)\) is not used on any already-colored neighbor. Assign such a color to \(v_i\). This preserves properness on all edges whose endpoints have been colored. Repeating for every \(i\) colors all vertices; when each edge is considered, its later-colored endpoint was assigned a color different from the endpoint colored before it. Thus the final coloring is proper and belongs to the lists. \(\square\)

The count is a “one more color than neighbors” argument, but its justification depends on the ordering: it is the already-colored neighbors that must be bounded. A PEO bounds the later neighbors, which is why the order is reversed.

Examples with Clique Size Three

The Bound and Its Scope

The theorem applies to arbitrary lists, not only to one common palette. At each step, the argument rules out the colors actually used on already-colored neighbors. It does not require the lists at different vertices to match, and it does not require those neighbors to use different colors. The clique property does imply that they receive distinct colors in a proper coloring, but the upper bound on forbidden colors follows even from the simpler count: there are at most \(\omega(G)-1\) neighbors to consider.

For a nonempty chordal graph, the bound is sharp in the uniform list-size sense. The theorem gives a coloring whenever every list has size at least \(\omega(G)\). Conversely, choose a clique of size \(\omega(G)\) and give every vertex in it the same list of \(\omega(G)-1\) colors. A proper coloring of that clique would need \(\omega(G)\) distinct colors, but only \(\omega(G)-1\) are available. So lists of that smaller size do not always suffice. In the standard notation for list chromatic number, this proves \(\chi_{\ell}(G)=\omega(G)\) for nonempty chordal graphs.

The empty graph has no vertices to color, so every list-coloring assertion about its vertices is vacuously satisfied; the theorem was stated for nonempty graphs to avoid choosing a convention for the clique number of the empty graph. Isolated vertices cause no difficulty: they have no already-colored neighbors, so any color in their nonempty list can be used. In a disconnected chordal graph, the PEO and reverse coloring argument apply to the entire graph, or component by component, because there are no edges between components.

Common Pitfall: Coloring in the Forward Order

A PEO controls each vertex’s later neighbors, not its earlier neighbors. Therefore the proof does not justify coloring \(v_1,v_2,\ldots,v_n\) in that order. For a concrete failure, take the star with \(V=\{x,y,z\}\), \(E=\{xz,yz\}\), and lists \(L(x)=L(y)=L(z)=\{\text{red},\text{blue}\}\). Its clique number is \(2\), and \(x,y,z\) is a PEO: each of \(x,y\) has the single later neighbor \(z\), while \(z\) has none.

If one incorrectly colors forward, one may assign red to \(x\) and blue to \(y\). Then both colors are forbidden at \(z\), so this particular partial coloring cannot be completed. That does not show the graph is not list-colorable: reverse order colors \(z\) first, say red, and then assigns blue to both \(x\) and \(y\), which are not adjacent. The correction is to match the direction of coloring to the neighbors controlled by the PEO. This example also shows why “a PEO exists” alone is not the coloring argument; the ordering must be used in reverse.