Consider the graph $G$ of order $n$ consisting of two disjoint cliques of even order $\frac{n}{2}=p+1$ (where $p$ is odd prime) joined by a bipartite graph (that is, deleting the edges of the two disjoint cliques from $G$ leaves a bipartite graph) of maximum degree $p$. Then, does the graph have list chromatic index $\le 2p+1$? The bipartite graph is also quite specific, in that it has one vertex in each partite set of degree exactly equal to $0,1,2,\dotsc,p$.


My view is that, by [Schauz - Proof of the list edge coloring conjecture for complete graphs of prime degree](https://doi.org/10.37236/4084) paper, we have that the disjoint cliques are chromatic edge-choosable. In addition, the edges joining the two cliques is a bipartite graph, which is again chromatic edge-choosable by the Galvin's theorem. Thus, it makes me think the above question has a positive answer. By the way, the graph has chromatic index equal to $2p$, that is the graph is of class $1$. Any hints?



List chromatic index of a particular graph
Greedy coloring works here to show $2p$-choosability, I believe, and the hypothesis that $p$ is prime doesn't appear to be necessary. Write the cliques as $A = \{a\_1, \ldots, a\_{p+1}\}$ and $B = \{b\_1, \ldots, b\_{p+1}\}$, taking the notation so that $a\_i$ has exactly $i-1$ neighbors in $B$ and vice versa.


First color the edges in the bigraph between $A$ and $B$; observe that each such edge is adjacent (in $L(G)$) to at most $2p-1$ previously colored edges when it is processed, thus has a color available. (Alternatively, just use Galvin's theorem for this part; then these edges only need to have lists of size $p$.)


Then color the edges $a\_ia\_j$ within $A$, ordering the edges so that $i + j$ is non-increasing. Observe that an edge $a\_ia\_j$ with $i \leq j$ has, within the clique $A$, exactly $p+1-j$ previously-colored adjacent edges at its $a\_i$-endpoint and $(p+1)-i-1 = p-i$ previously-colored adjacent edges at its $a\_j$-endpoint, for a total of $$2p+1-(i+j)$$ previously-colored adjacent edges within $A$. Furthermore, $a\_ia\_j$ has exactly $$(i-1) + (j-1) = i+j-2$$ previously-colored adjacent edges going to $B$. Thus, each edge $a\_ia\_j$ within $A$ is adjacent to exactly $2p-1$ previously-colored edges when it is processed, and therefore has a color available. Coloring $B$ the same way finishes the proof.


