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?

  • 1
    $\begingroup$ @GregoryJ.Puleo thanks! edited the post. $\endgroup$ – vidyarthi Jul 29 '20 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.

  • $\begingroup$ 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. $\endgroup$ – vidyarthi Jul 30 '20 at 18:00
  • $\begingroup$ 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 $\endgroup$ – vidyarthi Jul 30 '20 at 18:03
  • $\begingroup$ 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. $\endgroup$ – Gregory J. Puleo Jul 30 '20 at 18:46
  • $\begingroup$ ok, let us limit the degree of the bipartite graph to a maximum of $p$, then I think it should be possible,right? $\endgroup$ – vidyarthi Jul 30 '20 at 18:52
  • $\begingroup$ 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). $\endgroup$ – Gregory J. Puleo Jul 30 '20 at 18:55

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.