Assign a list L(x) of size two to every vertex x of an odd cycle. Show that there is an L-coloring unless all sets L(x) are the same.

Question

The problem above is from a midterm that I just took in my graph theory class and I didn't know how to answer it. I was hoping to get some tips to better understand the problem and write it out. Thank you in advance!

Answer 1

Start by finding two adjacent nodes whose lists are unequal. Say these are $v$ and $w$, where $v$ is clockwise of $w$. Assign to $v$ a color which is not present in $w$’s list. Then, starting with $v$’s clockwise neighbor, and proceeding clockwise around the cycle, assign each node a color different from their anti-clockwise neighbor. This is possible (why?). Furthermore, when you reach $w$ at the end, $w$’s color will be different from its anti-clockwise neighbor, and different from $v$ (because $v$’s color is not even in $w$’s list).