2
$\begingroup$

Prove that every odd cycle is $3$-choosable without using the fact that $\chi_l(G) \leq 1+ \Delta(G)$

Here is my attempt

Let $G$ be an odd cycle from by vertices $(v_1,v_2,\ldots,v_n,v_1)$. Since $G$ is an odd cycle $\chi(G)=3$ so $\chi_l(G) \geq 3$.

Now we only need to show that $\chi_l(G) \leq 3$. Note that $G$ is a cycle we can find a path $v_1,\ldots,v_{n-1}$ can be colored by 2 colors, such that $c(v_1) \not = c(v_{n-1})$ for every color list of size $3$. Now for the last vertex, namely $v_n$, since this is a cycle, every vertex has degree $2$, but every vertex is assigned color list of size $3$, so there is always at least one color available for $v_n$. Hence for every collection of color list of size $3$ , G can always be colored properly, thus $\chi_l(G) \leq 3$

this is how I understand the problem, but I'm not sure if my argument is correct enough. I would be very appreciated if any one would help me fixed any mistake I have made or make my argument flow better.

$\endgroup$

1 Answer 1

2
$\begingroup$

The basic idea is fine. Depending on the color lists, however, you may not be able to color the path $v_1,\ldots,v_{n-1}$ with just two colors, and it doesn’t matter whether $v_1$ and $v_{n-1}$ get the same color. All you really need to say is that since $v_n$ is adjacent only to $v_1$ and $v_{n-1}$ and has a color list of size $3$, there is always at least one color available for $v_n$ that is different from $c(v_1)$ and $c(v_{n-1})$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .