Edge choosability(edge list coloring) of bipartite graphs

427 Views Asked by At

It was proved by Galvin that the list chromatic index of bipartite multigraph $G$ equals to it's (ordinary) chromatic index: $$\chi_l'(G) = \chi'(G)$$ Let's use definition of choosability below:

enter image description here

I.e., for $K_{3,3}$, it's line graph $L(K_{3,3})$ is $(3, 1)-$ choosable.

enter image description here

Suppose we have list assignments to edges of $K_{3,3}$ and $f$ function definition like below: $$12 \rightarrow L_{1,2} \qquad |L_{1,2}| = 2 = f(12)\\ 14 \rightarrow L_{1,4} \qquad |L_{1,4}| = 2 = f(14)\\ 16 \rightarrow L_{1,6} \qquad |L_{1,6}| = 3 = f(16)\\ 32 \rightarrow L_{3,2} \qquad |L_{3,2}| = 2 = f(32) \\ 34 \rightarrow L_{3,4} \qquad |L_{3,4}| = 3 = f(34) \\ 36 \rightarrow L_{3,6} \qquad |L_{3,6}| = 2 = f(36) \\ 52 \rightarrow L_{5,2} \qquad |L_{5,2}| = 3 = f(52) \\ 54 \rightarrow L_{5,4} \qquad |L_{5,4}| = 2 = f(54) \\ 56 \rightarrow L_{5,6} \qquad |L_{5,6}| = 2 = f(56) \\ $$

I want to show that $L(K_{3,3})$ is $(f, 1)-$ choosable.
Or my understanding of $(f, g)-$choosability is not clear and the above statement can not be proved as $L(K_{3,3})$ is $(3, 1)-$ choosable.

1

There are 1 best solutions below

0
On BEST ANSWER

No, the graph $L(K_{3,3})$ is not $(f,1)$-choosable for the function $f$ defined in your question. To see this, consider a list-assignment where $L_{1,6}=\{a,b,c\}$, $L_{1,2}=L_{1,4}=\{a,b\}$, and $L_{3,6}=L_{5,6}=\{a,c\}$.