Prove that the even cycles are 2-list-colorable.

Question

I need to prove the statement in the title. It's very easy to show that with a particular 2-list-assignment, we can have a proper 2-list-coloring (e.g. with a greedy coloring algorithm). I'm just not sure if that's enough to show that the statement is true for ALL 2-list-assignments.

Here are the relevant definitions.

8.4.24. Definition. For each vertex $v$ in a graph $G$, let $L(v)$ denote a list of colors available at $v$. A list coloring or choice function is a proper coloring $f$ such that $f(v) \in L(v)$ for all $v$. A graph is $k$-choosable or list $k$-colorable if every assignment of $k$-element lists to the vertices permits a proper list coloring. The list chromatic number, choice number, or choosability $\chi_l(G)$ is the minimum $k$ such that $G$ is $k$-choosable.

Answer 1

There are actually some cases in which a greedy coloring algorithm will not work. For instance, suppose you have a $4$-cycle with the following color lists:

1. Red and blue
2. Red and green
3. Green and yellow
4. Red and yellow

A greedy algorithm will color vertex 1 red, then vertex 2 green, then vertex 3 yellow, and then get stuck: vertex 4 is adjacent to vertices 1 and 3, which are red and yellow respectively, so there is no way to color it.

It's possible to get this greedy algorithm "unstuck" by starting appropriately. If we began by coloring vertex 1 blue and then used the greedy algorithm, we would not run into the problem. (It's easy to see that we can get stuck only on the last vertex we color.) So you need a strategy for picking how to start, to avoid getting stuck on the last vertex.

Here's one possible strategy. (I urge you to think about it yourself before looking at the spoiler, because now you know what the problem is with the greedy strategy - and have the chance to figure out yourself how to avoid that problem.)

Pick two adjacent vertices $i, i+1$ which don't have the same color lists. Then color $i+1$ with a color not available for $i$ and proceed to color $i+2, i+3, \dots$ greedily. Each vertex other than the last vertex (vertex $i$) can be colored without problems. Vertex $i$ is guaranteed not to conflict with vertex $i+1$, so it also can be colored: at most one of its options is ruled out by the color of vertex $i-1$.

This works in all cases except when all vertices have the same color lists, in which case we're back in the world of ordinary 2-coloring, where we know what happens.