# Chapter 74. List Coloring

# Chapter 74. List Coloring

Ordinary graph coloring assumes that every vertex may use any color from a common set. List coloring changes this assumption. Each vertex is assigned its own list of allowed colors, and the coloring must choose a color from that list.

This transforms coloring from a global assignment problem into a constrained local assignment problem.

List coloring generalizes ordinary coloring and reveals a deeper structure behind graph colorability. Many graphs that are easy to color in the ordinary sense become difficult under list restrictions.

List coloring is also called choosability.

## 74.1 Motivation

Suppose a graph models scheduling constraints.

In ordinary coloring:

- every time slot is available for every task.

In practice, this is unrealistic. Some tasks may only be possible at certain times.

List coloring models this naturally.

Each vertex \(v\) receives a list:

$$
L(v)
$$

of allowable colors. A valid coloring must assign to \(v\) a color chosen from \(L(v)\).

Thus list coloring incorporates local restrictions directly into the coloring problem.

## 74.2 List Assignments

Let \(G=(V,E)\) be a graph.

A list assignment \(L\) assigns to every vertex \(v\in V\) a set:

$$
L(v)
$$

of allowed colors.

An \(L\)-coloring is a proper vertex coloring:

$$
c:V\to \bigcup_{v\in V}L(v)
$$

such that:

1. \(c(v)\in L(v)\),
2. adjacent vertices receive different colors.

Thus:

$$
uv\in E
\quad\Longrightarrow\quad
c(u)\ne c(v).
$$

The graph is \(L\)-colorable if such a coloring exists.

## 74.3 \(k\)-Choosability

A graph \(G\) is \(k\)-choosable if:

For every assignment of lists satisfying

$$
|L(v)|\ge k
$$

for all vertices \(v\), the graph admits an \(L\)-coloring.

Thus the graph remains colorable no matter how the lists are chosen, provided every list has size at least \(k\).

The least integer \(k\) for which \(G\) is \(k\)-choosable is called the list chromatic number, or choice number, denoted:

$$
\chi_\ell(G).
$$

\chi_\ell(G)=\min\{k:G\text{ is }k\text{-choosable}\}

This parameter generalizes ordinary chromatic number.

## 74.4 Relation to Ordinary Coloring

Every ordinary coloring problem is a special case of list coloring.

If every vertex receives the same list:

$$
L(v)=\{1,2,\ldots,k\},
$$

then an \(L\)-coloring is exactly an ordinary \(k\)-coloring.

Therefore:

$$
\chi(G)\le \chi_\ell(G).
$$

\chi(G)\le\chi_\ell(G)

List coloring can only be harder than ordinary coloring.

In many graphs the two parameters are equal. In others they differ substantially.

## 74.5 First Examples

### Complete Graphs

For \(K_n\):

$$
\chi(K_n)=n.
$$

Also:

$$
\chi_\ell(K_n)=n.
$$

Indeed, if every vertex has a list of size \(n-1\), one can choose identical lists and force a conflict.

Thus complete graphs behave the same in ordinary and list coloring.

### Bipartite Graphs

Bipartite graphs satisfy:

$$
\chi(G)=2.
$$

However, their list chromatic numbers can be arbitrarily large.

This is one of the most important differences between ordinary and list coloring.

Thus list coloring reveals complexity invisible to ordinary chromatic number.

## 74.6 Even Cycles

Consider an even cycle \(C_{2m}\).

Since the graph is bipartite:

$$
\chi(C_{2m})=2.
$$

It is also true that:

$$
\chi_\ell(C_{2m})=2.
$$

Thus even cycles remain 2-colorable even under arbitrary lists of size 2.

Cycles therefore behave similarly in ordinary and list coloring.

## 74.7 Odd Cycles

For odd cycles:

$$
\chi(C_{2m+1})=3.
$$

Also:

$$
\chi_\ell(C_{2m+1})=3.
$$

Thus ordinary and list coloring coincide for cycles.

The difference between chromatic number and list chromatic number appears in more complicated graphs.

## 74.8 A Bipartite Example

One of the most surprising facts in list coloring is:

There exist bipartite graphs with arbitrarily large list chromatic number.

Thus:

$$
\chi(G)=2
$$

does not imply small \(\chi_\ell(G)\).

This sharply contrasts with ordinary coloring theory.

The phenomenon shows that list coloring measures a fundamentally different kind of complexity.

## 74.9 Hall's Theorem and List Coloring

List coloring is closely connected with matching theory.

Suppose each vertex has a list of allowable colors. One may think of vertices as requesting colors from available options.

Under certain conditions, Hall's Marriage Theorem guarantees a valid assignment.

This connection becomes especially important in bipartite graphs and edge-list-coloring problems.

Matching theory therefore plays a major role in list coloring proofs.

## 74.10 Greedy List Coloring

Greedy coloring extends naturally to list coloring.

Suppose the vertices are ordered:

$$
v_1,v_2,\ldots,v_n.
$$

When coloring \(v_i\), at most \(d(v_i)\) colors are forbidden by already colored neighbors.

Therefore, if:

$$
|L(v_i)|>d(v_i),
$$

then at least one available color remains.

This gives a sufficient condition for list colorability.

In particular, every graph satisfies:

$$
\chi_\ell(G)\le \Delta(G)+1.
$$

\chi_\ell(G)\le\Delta(G)+1

The proof is the same greedy argument used in ordinary coloring.

## 74.11 Degeneracy and Choosability

If a graph is \(d\)-degenerate, then every subgraph contains a vertex of degree at most \(d\).

Using a smallest-last ordering, greedy list coloring gives:

$$
\chi_\ell(G)\le d+1.
$$

Thus sparse graphs often have small choice number.

For example:

| Graph class | Degeneracy | Choice number bound |
|---|---:|---:|
| Forests | 1 | 2 |
| Planar graphs | 5 | 6 |

Degeneracy arguments are among the most useful general tools in list coloring.

## 74.12 Planar Graphs

Ordinary planar coloring satisfies:

$$
\chi(G)\le 4.
$$

List coloring behaves differently.

There exist planar graphs that are not 4-choosable.

However, every planar graph is 5-choosable.

This theorem was proved by Paul Erdős, Arthur Rubin, and Herbert Taylor.

Thus list coloring is strictly harder than ordinary coloring even for planar graphs.

## 74.13 Choice Number vs Chromatic Number

The gap between:

$$
\chi(G)
$$

and

$$
\chi_\ell(G)
$$

can be arbitrarily large.

This makes list coloring fundamentally richer than ordinary coloring.

Typical behavior:

| Graph | \(\chi(G)\) | \(\chi_\ell(G)\) |
|---|---:|---:|
| Complete graph \(K_n\) | \(n\) | \(n\) |
| Tree | 2 | 2 |
| Even cycle | 2 | 2 |
| Certain bipartite graphs | 2 | arbitrarily large |

Thus ordinary colorability does not fully capture local coloring difficulty.

## 74.14 Edge List Coloring

List coloring also applies to edge coloring.

Each edge receives a list of allowed colors. Adjacent edges must receive different colors.

The edge-list chromatic number is denoted:

$$
\chi'_\ell(G).
$$

This leads to the List Coloring Conjecture:

For every graph \(G\),

$$
\chi'_\ell(G)=\chi'(G).
$$

This conjecture remains open in general.

It is one of the major unsolved problems in graph coloring theory.

## 74.15 Online List Coloring

List coloring has dynamic variants.

In online list coloring:

- lists are revealed gradually,
- colors must be chosen immediately,
- previous choices cannot be changed.

This models real-time scheduling and adaptive resource allocation.

Online coloring is generally harder than offline list coloring.

## 74.16 Probabilistic Methods

Probabilistic methods play a major role in list coloring.

Random list assignments can create severe local conflicts even in sparse graphs.

Many important lower bounds for choice number are proved probabilistically.

Probabilistic techniques introduced by Paul Erdős strongly influenced modern list coloring theory.

## 74.17 Algebraic Methods

List coloring also has powerful algebraic techniques.

One of the most famous is the Combinatorial Nullstellensatz of Noga Alon.

This method converts coloring questions into polynomial existence problems.

Algebraic tools have produced major advances in choosability theory.

## 74.18 Applications

List coloring models systems with local restrictions.

Typical applications include:

| Application | Meaning of lists |
|---|---|
| Scheduling | Allowed times |
| Frequency assignment | Available frequencies |
| Register allocation | Allowed registers |
| Resource allocation | Local constraints |
| Wireless communication | Interference restrictions |

Ordinary coloring assumes globally interchangeable resources. List coloring allows heterogeneous constraints.

This often gives a more realistic model.

## 74.19 Structural Themes

List coloring illustrates several major graph-theoretic principles.

### Local Restrictions Matter

Global color availability is less important than local compatibility.

### Sparse Graphs Behave Better

Low-degree and low-degeneracy graphs often have small choice number.

### Ordinary Coloring Is Incomplete

Graphs with small chromatic number may still be difficult to list color.

### Algebra and Probability Become Important

Many ordinary coloring arguments fail in list coloring and require deeper techniques.

## 74.20 Summary

List coloring generalizes ordinary graph coloring by assigning each vertex its own allowable color set.

The central parameter is the choice number:

\chi_\ell(G)

which measures the minimum list size guaranteeing colorability.

The main ideas are:

| Concept | Meaning |
|---|---|
| List assignment | Allowed colors for each vertex |
| \(L\)-coloring | Proper coloring from lists |
| \(k\)-choosable | Colorable for every list assignment of size \(k\) |
| Choice number | Minimum guaranteed list size |
| Relation to coloring | \(\chi(G)\le\chi_\ell(G)\) |

List coloring reveals a deeper layer of graph coloring theory. It shows that ordinary chromatic number does not fully describe coloring complexity when local restrictions are introduced.

## 74.21 Exercises

1. Define an \(L\)-coloring.

2. Define the choice number of a graph.

3. Prove that:

$$
\chi(G)\le\chi_\ell(G).
$$

4. Show that:

$$
\chi_\ell(K_n)=n.
$$

5. Prove that trees are 2-choosable.

6. Show that even cycles are 2-choosable.

7. Explain why list coloring is harder than ordinary coloring.

8. Describe a scheduling problem modeled naturally by list coloring.

9. Prove that:

$$
\chi_\ell(G)\le\Delta(G)+1.
$$

10. Explain why degeneracy gives choosability bounds.

11. State the List Coloring Conjecture.

12. Compare planar graph coloring with planar list coloring.

13. Explain the role of Hall's Theorem in list coloring.

14. Describe an application where vertices have different allowable colors.

15. Explain why bipartite graphs may still have large choice number.