4
$\begingroup$

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).

$\endgroup$
  • 1
    $\begingroup$ 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). $\endgroup$ – Sasho Nikolov Jun 18 '14 at 15:25
  • 1
    $\begingroup$ 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)}$. $\endgroup$ – Sasho Nikolov Jun 18 '14 at 17:17
  • $\begingroup$ @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. $\endgroup$ – joro Jun 19 '14 at 5:38
  • $\begingroup$ 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. $\endgroup$ – Sasho Nikolov Jun 19 '14 at 14:43
  • $\begingroup$ @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? $\endgroup$ – joro Jun 19 '14 at 14:47

Your Answer

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

Browse other questions tagged or ask your own question.