# List chromatic index of a particular graph

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 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?

• @GregoryJ.Puleo thanks! edited the post. Jul 29, 2020 at 22:04

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.
• great! but I think first coloring the edges of $A$ (or $B$) and then the edges of the bipartite graph and lastly $B$ (or $A$) would also work. But, for this, I would use the paer refereed and the Galvin' stheorem. Jul 30, 2020 at 18:00
• by the way, would replacing the bipartite graph with arbitrary bipartite graph have any effect (I dont think so)? If so, then I think we could extend this method to prove edge chromatic choosability for all graphs with maximum degree$\ge\frac{n}{2}$, whre $n$ is the order of the graph Jul 30, 2020 at 18:03
• The degree constraint is essential here for arguing that each edge has few enough previously-colored adjacent edges going to $B$. In the extreme case where the bipartite graph was $K_{p+1, p+1}$, the whole graph would just be $K_{2p+2}$, and then no matter how you slice it the last edge you consider will have $2(2p+1) - 1 = 4p+1$ previously-colored adjacent edges. Jul 30, 2020 at 18:46
• ok, let us limit the degree of the bipartite graph to a maximum of $p$, then I think it should be possible,right? Jul 30, 2020 at 18:52
• I suspect there would still be far too many previously-colored adjacent edges for the late edges within $A$. Note that the last edge considered within $A$ will have $2p-1$ previously-colored adjacent edges just within $A$, and therefore couldn't afford to be incident to any edges going to $B$. I think the only way to relax the hypothesis you stated in the question and have this proof still go through is to allow vertex $a_i$ to have degree at most $i-1$ in $B$, rather than degree exactly $i-1$ (and likewise for $B$-vertices). Jul 30, 2020 at 18:55