<p>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.</p>

<ol>
<li>What is the complexity of edge coloring graphs in $C$?</li>
<li>Is there a reduction from SAT to edge coloring graphs in $C$?</li>
</ol>

<p>Related to <a href="https://cstheory.stackexchange.com/questions/24927/the-overfull-conjecture-in-graph-theory-and-conp">this question</a>. 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.</p>

<p>Possible approach is using some gadget like <a href="http://www.or.uni-bonn.de/~hougardy/paper/girthall.pdf" rel="nofollow noreferrer">here</a></p>

<p>In addition this might help for counterexample for the conjecture (if false).</p>

CC BY-SA 3.0
2014-06-18T15:25:20.373Z
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
CC BY-SA 3.0
2014-06-18T17:17:39.977Z
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
CC BY-SA 3.0
2014-06-19T05:38:51.710Z
@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
CC BY-SA 3.0
2014-06-19T14:43:27.337Z
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
CC BY-SA 3.0
2014-06-19T14:47:47.693Z
@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
CC BY-SA 3.0
2014-06-19T14:50:54.903Z
What you are missing (or I am not understanding you) is that a reduction to edge coloring graphs in $C$ is not sufficient for this. You need a reduction to deciding if the edge chromatic number of a graph $G$ in $C$ is at most $\Delta(G)$. This may be a much easier problem than edge coloring graphs in $C$. Is it clear now?
Sasho Nikolov
CC BY-SA 3.0
2014-06-19T15:05:58.010Z
@SashoNikolov there is reduction from SAT to "Is 3-regular graph 3-EC". I am asking for reduction "SAT -> Is graph in C Class 1". As explained in the other question, the decision problem "is graph in C class 1", is NOT IN coNP since in both cases short certificates exist. Either Class 1 coloring (SAT instance of EC) xor existence of certain subgraph, which while hard is certainly not in coNP since the subgraph is certificate. Assuming the conjecture.
joro
CC BY-SA 3.0
2014-06-19T16:59:30.087Z
A problem can be in coNP and have short certificates for yes instances. What it is unlikely to be (unless NP = coNP) is coNP hard. All I am saying is that "is the graph $G$ in $C$ class 1" is a decision problem potentially much easier than the optimization problem of minimizing edge chromatic number of graphs in $C$. Which is why I find the wording of the question slightly problematic. I will let this be my last comment on the issue, I hope you understand what I mean.
Sasho Nikolov
CC BY-SA 4.0
2019-11-16T10:43:56.210Z
Crossposted on MO: https://mathoverflow.net/questions/346086/complexity-of-edge-coloring-graphs-with-deltag-ge-n-3-assuming-the-overful
joro
<cc.complexity-theory><graph-theory>
Complexity of edge coloring graphs with $\Delta(G) \ge n/3$
joro
# Complexity of edge coloring graphs with $\Delta(G) \ge n/3$

(Asked by: username_0 on 2014-06-18)

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](https://cstheory.stackexchange.com/questions/24927/the-overfull-conjecture-in-graph-theory-and-conp). 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](http://www.or.uni-bonn.de/~hougardy/paper/girthall.pdf)

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

**Tags:** cc.complexity-theory, graph-theory

> **Comments:**
> **username_1**: 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).  
> **username_1**: 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)}$.  
> **username_0**: @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.  
> **username_1**: 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.  
> **username_0**: @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?  
> **username_1**: What you are missing (or I am not understanding you) is that a reduction to edge coloring graphs in $C$ is not sufficient for this. You need a reduction to deciding if the edge chromatic number of a graph $G$ in $C$ is at most $\Delta(G)$. This may be a much easier problem than edge coloring graphs in $C$. Is it clear now?  
> **username_0**: @SashoNikolov there is reduction from SAT to "Is 3-regular graph 3-EC". I am asking for reduction "SAT -> Is graph in C Class 1". As explained in the other question, the decision problem "is graph in C class 1", is NOT IN coNP since in both cases short certificates exist. Either Class 1 coloring (SAT instance of EC) xor existence of certain subgraph, which while hard is certainly not in coNP since the subgraph is certificate. Assuming the conjecture.  
> **username_1**: A problem can be in coNP and have short certificates for yes instances. What it is unlikely to be (unless NP = coNP) is coNP hard. All I am saying is that "is the graph $G$ in $C$ class 1" is a decision problem potentially much easier than the optimization problem of minimizing edge chromatic number of graphs in $C$. Which is why I find the wording of the question slightly problematic. I will let this be my last comment on the issue, I hope you understand what I mean.  
> **username_0**: Crossposted on MO: https://mathoverflow.net/questions/346086/complexity-of-edge-coloring-graphs-with-deltag-ge-n-3-assuming-the-overful  

---

## 0 answers

