5
$\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).

Improve this question
$\endgroup$
9
  • 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
    Commented Jun 18, 2014 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
    Commented Jun 18, 2014 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
    Commented Jun 19, 2014 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
    Commented Jun 19, 2014 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
    Commented Jun 19, 2014 at 14:47

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.