<p>For the possible reduction you are mentioning, if you find such a reduction from SAT to this particular edge-coloring problem, and additionnally you assume OC, then it would indeed mean  <strong>NP</strong> $=$ co-<strong>NP</strong>. However, it would be very surprising:   it would mean that basically, up to encoding, you found a way to always provide a short certificate that a formula is not satisfiable.
This seems quite unlikely to reach with a simple construction.</p>

CC BY-SA 3.0
2014-06-18T09:22:47.033Z
Thank you. So if there is SAT reduction to it (as I asked) then SAT/UNSAT in NP ∩ co-NP?
joro
CC BY-SA 3.0
2014-06-18T09:34:42.357Z
Actually I misunderstood your question earlier, my answer above does not answer it. So here it is: yes it seems so, but it would be very surprising. It would mean that basically, up to encoding, you found a way to always provide a short certificate that a formula is not satisfiable.
Denis
CC BY-SA 3.0
2014-06-18T09:41:43.680Z
Thank you. I don't claim it is likely both to happen (Conjecture true & SAT reduction). Though I don't find it unlikely reduction to be possible, since this will mean large degree graphs are easy to edge color (this is counterintuitive to me).
joro
CC BY-SA 3.0
2014-06-18T14:05:27.117Z
FYI asked about if reduction is possible and added to the question proven special case of OC.
joro
CC BY-SA 3.0
2014-06-18T15:20:55.410Z
Note that high degree graphs could still be hard to edge color with an optimal number of colors. It might just be easy to decide if $\Delta(G)$ colors are enough. Even this doesn't have to be the case: a problem in $\mathsf{NP} \cap \mathsf{coNP}$ doesn't have to  be easy, as far as we know $\mathsf{P} \neq \mathsf{NP} \cap \mathsf{coNP}$ and we don't know an efficient algorithm for factoring yet.
Sasho Nikolov
CC BY-SA 3.0
2014-06-18T16:29:41.283Z
same goes for parity games
Denis
CC BY-SA 3.0
2014-06-19T05:41:49.150Z
@SashoNikolov if you disagree with this answer, please give another answer :) I don't think $\mathsf{P} \neq \mathsf{NP} \cap \mathsf{coNP}$ is unconditionally known for the simple reason we don't know $P \ne NP$ (and factoring might be in $P$ for other reasons).
joro
CC BY-SA 3.0
2014-06-19T14:36:03.153Z
I don't disagree with the answer, I disagree with your comment that a reduction as in your question is plausible because otherwise "this will mean that large degree graphs are easy to edge color". The specific decision problem you are asking about may be easier than edge coloring large degree graphs, and not being NP-hard does not necessarily mean being easy. Whether $\mathsf{P} = \mathsf{NP} \cap \mathsf{coNP}$ is unknown even conditional on $\mathsf{P} \neq \mathsf{NP}$.
Sasho Nikolov
CC BY-SA 3.0
2014-06-19T15:31:30.540Z
@SashoNikolov OK, I well might be wrong on "...easy to color...".
joro
CC BY-SA 3.0
2014-06-18T09:17:21.293Z
2014-06-18T09:45:17.893Z
2014-06-18T09:45:17.893Z
Denis
<p>I am not good at complexity, but got a possible
relation between a plausible conjecture in graph
theory and $coNP$.</p>

<p>Graph $G$ is Class 1 if it can be edge colored
with $\Delta(G)$ colors, otherwise it is Class 2 and
can be edge colored with $\Delta(G) + 1$ colors.</p>

<p>The <a href="https://en.wikipedia.org/wiki/Overfull_conjecture" rel="nofollow">Overfull conjecture (OC)</a>
asserts</p>

<blockquote>
  <p>A graph G with $\Delta (G) \geq n/3$ is class 2 <strong>if and only if</strong> it has an overfull subgraph $S$ such that $\displaystyle \Delta (G) = \Delta (S)$.</p>
</blockquote>

<p>Assume OC and $\Delta (G) \geq n/3$.</p>

<p>This means that we have short certificate if $G$ is Class 1
or Class 2.</p>

<p>For Class 1 the certificate is $\Delta(G)$ edge coloring finding it is in $NP$.</p>

<p>For Class 2 the certificate is overfull subgraph $S$ such that $\displaystyle \Delta (G) = \Delta (S)$ and finding it is in $NP$.</p>

<p>This means there are no $coNP$-hard problems in this case.</p>

<p>There is a reduction from SAT to edge coloring
$3$-regular graphs. Encoding unsatisfiable CNF
to edge coloring is UNSAT and UNSAT is in $coNP$.</p>

<blockquote>
  <p>Question:  Does the overfull conjecture and reduction
  from SAT to edge coloring $G$ with $\Delta (G) \geq n/3$
  imply $NP=coNP$?</p>
</blockquote>

<p>According to a <a href="http://www.or.uni-bonn.de/~hougardy/paper/girthall.pdf" rel="nofollow">paper</a>
edge coloring is NP-complete (possibly minor abuse of terminology) for
$r$-regular graphs for any fixed $r \ge 3$ and it gives reduction
of $G$ to $r$-regular $G'$.</p>

<p>Positive answer might help for counterexample to the
overfull conjecture.</p>

<p>$\Delta(G)$ is the maximum degree and $n$ is the number of
vertices.</p>

<hr>

<p><strong>EDIT</strong> Special cases of OC are proven.</p>

<p>According to <a href="http://onlinelibrary.wiley.com/doi/10.1002/jgt.20013/abstract" rel="nofollow">Overfull Conjecture for Graphs with High Minimum Degree,
Michael Plantholt</a>:</p>

<blockquote>
  <p>we show that any (not necessarily regular) graph $G$ of even order $n$ that has sufficiently high minimum degree $\delta(G) \ge (\sqrt{7}/3) n$  has chromatic index equal to its maximum degree providing that $G$ does not contain an
  "overfull" subgraph, that is, a subgraph which trivially forces the chromatic
  index to be more than the maximum degree. This result thus verifies the
  Overfull Conjecture for graphs of even order and sufficiently high minimum
  degree.</p>
</blockquote>

<p><strong>EDIT 2</strong>
<a href="http://people.idsia.ch/~laekhanukit/paper/powergraph.pdf" rel="nofollow">This paper p.2</a>
might be related since it claims unless $NP=ZPP$, one can't
approximate $\chi'(L^k(G))$ where $L^k(G)$ is the $k-th$ power of
the line graph of $G$. (might be wrong on this since $\chi'$ is either
$\Delta$ or $\Delta+1$).</p>

CC BY-SA 3.0
2014-06-18T08:31:27.357Z
If there non-critical mistakes in the question I would appreciate help for fixing them.
joro
CC BY-SA 4.0
2019-11-16T10:44:33.270Z
Similar question 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><graph-colouring>
The Overfull conjecture in graph theory and $coNP$
joro
# The Overfull conjecture in graph theory and $coNP$

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

I am not good at complexity, but got a possible
relation between a plausible conjecture in graph
theory and $coNP$.

Graph $G$ is Class 1 if it can be edge colored
with $\Delta(G)$ colors, otherwise it is Class 2 and
can be edge colored with $\Delta(G) + 1$ colors.

The [Overfull conjecture (OC)](https://en.wikipedia.org/wiki/Overfull_conjecture)
asserts

> A graph G with $\Delta (G) \geq n/3$ is class 2 **if and only if** it has an overfull subgraph $S$ such that $\displaystyle \Delta (G) = \Delta (S)$.

Assume OC and $\Delta (G) \geq n/3$.

This means that we have short certificate if $G$ is Class 1
or Class 2.

For Class 1 the certificate is $\Delta(G)$ edge coloring finding it is in $NP$.

For Class 2 the certificate is overfull subgraph $S$ such that $\displaystyle \Delta (G) = \Delta (S)$ and finding it is in $NP$.

This means there are no $coNP$-hard problems in this case.

There is a reduction from SAT to edge coloring
$3$-regular graphs. Encoding unsatisfiable CNF
to edge coloring is UNSAT and UNSAT is in $coNP$.

> Question: Does the overfull conjecture and reduction
> from SAT to edge coloring $G$ with $\Delta (G) \geq n/3$
> imply $NP=coNP$?

According to a [paper](http://www.or.uni-bonn.de/~hougardy/paper/girthall.pdf)
edge coloring is NP-complete (possibly minor abuse of terminology) for
$r$-regular graphs for any fixed $r \ge 3$ and it gives reduction
of $G$ to $r$-regular $G'$.

Positive answer might help for counterexample to the
overfull conjecture.

$\Delta(G)$ is the maximum degree and $n$ is the number of
vertices.

---

**EDIT** Special cases of OC are proven.

According to [Overfull Conjecture for Graphs with High Minimum Degree,
Michael Plantholt](http://onlinelibrary.wiley.com/doi/10.1002/jgt.20013/abstract):

> we show that any (not necessarily regular) graph $G$ of even order $n$ that has sufficiently high minimum degree $\delta(G) \ge (\sqrt{7}/3) n$ has chromatic index equal to its maximum degree providing that $G$ does not contain an
> "overfull" subgraph, that is, a subgraph which trivially forces the chromatic
> index to be more than the maximum degree. This result thus verifies the
> Overfull Conjecture for graphs of even order and sufficiently high minimum
> degree.

**EDIT 2**
[This paper p.2](http://people.idsia.ch/~laekhanukit/paper/powergraph.pdf)
might be related since it claims unless $NP=ZPP$, one can't
approximate $\chi'(L^k(G))$ where $L^k(G)$ is the $k-th$ power of
the line graph of $G$. (might be wrong on this since $\chi'$ is either
$\Delta$ or $\Delta+1$).

**Tags:** cc.complexity-theory, graph-theory, graph-colouring
> **Comments:**
> **username_0**: If there non-critical mistakes in the question I would appreciate help for fixing them.  
> **username_0**: Similar question on MO: https://mathoverflow.net/questions/346086/complexity-of-edge-coloring-graphs-with-deltag-ge-n-3-assuming-the-overful  

---

## 1 answers

### Answer by username_1 on 2014-06-18. Score: 5 | Accepted answer

For the possible reduction you are mentioning, if you find such a reduction from SAT to this particular edge-coloring problem, and additionnally you assume OC, then it would indeed mean **NP** $=$ co-**NP**. However, it would be very surprising: it would mean that basically, up to encoding, you found a way to always provide a short certificate that a formula is not satisfiable.
This seems quite unlikely to reach with a simple construction.

> **Comments:**
> **username_0**: Thank you. So if there is SAT reduction to it (as I asked) then SAT/UNSAT in NP ∩ co-NP?  
> **username_1**: Actually I misunderstood your question earlier, my answer above does not answer it. So here it is: yes it seems so, but it would be very surprising. It would mean that basically, up to encoding, you found a way to always provide a short certificate that a formula is not satisfiable.  
> **username_0**: Thank you. I don't claim it is likely both to happen (Conjecture true & SAT reduction). Though I don't find it unlikely reduction to be possible, since this will mean large degree graphs are easy to edge color (this is counterintuitive to me).  
> **username_0**: FYI asked about if reduction is possible and added to the question proven special case of OC.  
> **username_2**: Note that high degree graphs could still be hard to edge color with an optimal number of colors. It might just be easy to decide if $\Delta(G)$ colors are enough. Even this doesn't have to be the case: a problem in $\mathsf{NP} \cap \mathsf{coNP}$ doesn't have to  be easy, as far as we know $\mathsf{P} \neq \mathsf{NP} \cap \mathsf{coNP}$ and we don't know an efficient algorithm for factoring yet.  
> **username_1**: same goes for parity games  
> **username_0**: @SashoNikolov if you disagree with this answer, please give another answer :) I don't think $\mathsf{P} \neq \mathsf{NP} \cap \mathsf{coNP}$ is unconditionally known for the simple reason we don't know $P \ne NP$ (and factoring might be in $P$ for other reasons).  
> **username_2**: I don't disagree with the answer, I disagree with your comment that a reduction as in your question is plausible because otherwise "this will mean that large degree graphs are easy to edge color". The specific decision problem you are asking about may be easier than edge coloring large degree graphs, and not being NP-hard does not necessarily mean being easy. Whether $\mathsf{P} = \mathsf{NP} \cap \mathsf{coNP}$ is unknown even conditional on $\mathsf{P} \neq \mathsf{NP}$.  
> **username_0**: @SashoNikolov OK, I well might be wrong on "...easy to color...".  

---

