1
$\begingroup$

Suppose, we know that $G$ is a regular graph of odd order that is $k$- edge choosable, where $k$ is the degree. Then, is it true that $\overline{G}$ has list edge chromatic number at most $n-k+1$?

I think the answer is yes. This is because, by Haggkvist-Janssen theorem, we have that the complete graph of odd order has list chromatic index $n$, where $n$ is the order. Thus, if edge choosability of $G$ is $k$, then it is straightforward to see that $\overline{G}$ has list edge chromatic number at most $n-k+1$ by a greedy approach. If this be true, we need to obtain only the list chromatic indices of graphs with $\Delta\ge\frac{n}{2}$, where $\Delta$ is the maximum degree. Am I right, or are there counterexamples? Thanks beforehand.

$\endgroup$
8
  • $\begingroup$ Is $n$ the number of vertices of $G$? If so, isn't a 5-cycle $G$ 3-edge choosable, but $\bar{G}$ (which is isomorphic to $G$) is not 2-edge choosable? $\endgroup$ Commented Aug 23, 2020 at 13:38
  • $\begingroup$ @RichardStanley yes, what if I put the upper bound at $n-k+1$? edited the post $\endgroup$
    – vidyarthi
    Commented Aug 23, 2020 at 16:07
  • $\begingroup$ @bof again edited the post. see now $\endgroup$
    – vidyarthi
    Commented Aug 24, 2020 at 19:42
  • $\begingroup$ @bof The reference is not strictly peer-reviewed. So I thought it may not be exact. Hence, you need not have deleted your answer $\endgroup$
    – vidyarthi
    Commented Aug 25, 2020 at 9:57
  • $\begingroup$ I deleted my answer because it seemed to me that I was not telling you anything you did not already know. It was hard to tell what you knew and what you didn't know, because the question, in my opinion, was not formulated with great precision and clarity and was continually being revised. $\endgroup$
    – bof
    Commented Aug 25, 2020 at 13:40

0

You must log in to answer this question.

Browse other questions tagged .