6
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ @GregoryJ.Puleo thanks! edited the post. $\endgroup$
    – vidyarthi
    Commented Jul 29, 2020 at 22:04

1 Answer 1

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\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
    Commented Jul 30, 2020 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
    Commented Jul 30, 2020 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
    Commented Jul 30, 2020 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
    Commented Jul 30, 2020 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
    Commented Jul 30, 2020 at 18:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .