I have 2 cycles with 6 length as shown below.

enter image description here

I want to show that the above graph is 4-edge-choosable. I don't know where to start. It's known that every cycle of even length is 2-edge-choosable, therefore, we can color one of these cycles(suppose we are coloring red one) at first and at each vertice of that cycle we'll have 2 permissible colors to color other cycle(in our case blue one). But what can we do when for example permissible colors at vertex $6$ are colors that are choosen for edges $23$ and $34$, i.e.

We have colored edges of red cycle with these colors:

$$16 \rightarrow \alpha_1 \\ 23 \rightarrow \alpha_2 \\ ...\\ 61 \rightarrow \alpha_6$$

Suppose that list of colors for $63$ edge is $L = $ { $ \beta_1, \beta_2, \beta_3, \beta_4$} and now for $63$ edge we have
$L' = L\setminus ${$\alpha_5, \alpha_6 $} 2 permissible colors when we are looking from the vertex $6$ and from the other side we have $L'' = L\setminus ${$\alpha_2, \alpha_3 $} 2 permissible colors when we are looking from the vertex $3$. What if $L' = ${$\alpha_2, \alpha_3$} and $L'' = ${$\alpha_5, \alpha_6$}. How can we color edges of first(red) cycle so that we shouldn't get the latter situation? Or maybe color them dynamically, by changing edge colors when starting second cycle coloring?

Thanks in advance.

  • $\begingroup$ I don't know how to do this, so this is just an idea for 'where to start'. Do you understand why an even length cycle is 2-edge-choosable? That is, do you know what the key point of the proof is? There you need to avoid finding that the two colours for the last edge already occur on the two adjacent edges. Maybe similar ideas will help in this case. $\endgroup$ – Jessica B Jul 3 '14 at 16:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.