# Complexity of edge coloring graphs with $\Delta(G) \ge n/3$

Let $C$ be the class of graphs satisfying $\Delta(G) \ge n/3$, where $\Delta(G)$ is the maximum degree of a graph $G$, and $n$ denotes the number of vertices.

1. What is the complexity of edge coloring graphs in $C$?
2. Is there a reduction from SAT to edge coloring graphs in $C$?

Related to this question. A positive answer means a plausible graph theory conjecture implies $\sf NP=coNP$. A negative answer would greatly surprise me since all graphs of sufficiently large degree will be efficiently edge-colorable.

Possible approach is using some gadget like here

In addition this might help for counterexample for the conjecture (if false).

• As I mentioned in a comment to the other question, to contradict the conjecture (assuming $\mathsf{NP} \neq \mathsf{coNP}$) you need to show it is $\mathsf{NP}$-hard to decide if the edge chromatic number of $G$ is at most $\Delta(G)$. This may not be the case but computing the edge chromatic number could still be $\mathsf{NP}$-hard (because say it's $\mathsf{NP}$-hard to decide if $3$ colors are enough). – Sasho Nikolov Jun 18 '14 at 15:25
• To illustrate this kind of phenomenon, the gap closest vector problem in $n$-dimensional lattices is in $\mathsf{NP} \cap \mathsf{coNP}$ when the gap is $O(\sqrt{n})$ and is $\mathsf{NP}$-hard when the gap is $n^{o(1)}$. – Sasho Nikolov Jun 18 '14 at 17:17
• @SashoNikolov to contradict the conjecture is enough to show a counterexample, no matter if NP=coNP or not. If a SAT reduction exists, I suspect the reduction will give explicit counterexamples if NP \ne coNP. – joro Jun 19 '14 at 5:38
• Of course it's enough to give a counterexample. My point is that this sentence in the question is not strictly correct: "A positive answer means a plausible graph theory conjecture implies 𝖭𝖯=𝖼𝗈𝖭𝖯." It doesn't, because a reduction showing edge coloring graphs in $C$ is NP-hard doesn't necessarily have to show it is NP-hard to decide of $\Delta$ colors are sufficient. This particular decision problem is not equivalent to the minimization problem. – Sasho Nikolov Jun 19 '14 at 14:43
• @SashoNikolov What I meant was "reduction from SAT + conjecture imply NP=coNP". Reduction from SAT + conjecture gives short certificate for UNSAT when the CNF is UNSAT or am I missing something? – joro Jun 19 '14 at 14:47