<p>A graph is <a href="http://dml.cz/bitstream/handle/10338.dmlcz/140801/CzechMathJ_60-2010-4_11.pdf">weakly perfect</a> if the clique number equals the chromatic
number, i.e. $\omega(G)=\chi(G)$. Deciding membership is NP-complete
according to the paper.</p>

<p>Because of the inequality $\omega(G) \le \chi(G)$ a $k$-clique is certificate
that there isn't smaller than $k$ coloring.</p>

<blockquote>
  <p>What is the complexity of deciding if a weakly perfect graph is
  $k$-colorable?</p>
</blockquote>

<hr>

<p>Appears to me it might not be NP-complete because the certificate
will involve co-NP.</p>

<p>Also it might not be in P since it will decide coloring graphs for which
the inequality happens "by chance" and possibly by adding disjoint
cliques might be improved.</p>

<p>Searching the web found algebraic constructions of weakly perfect.
In all papers coloring was polynomial via closed form.</p>

<p>Related to <a href="https://mathoverflow.net/questions/194431/graph-classes-where-finding-explicit-coloring-have-certificate-that-it-is-minumu">this</a>.</p>

CC BY-SA 3.0
2015-01-23T09:34:22.717Z
A standard assumption in complexity theory is that well-formed inputs are easy to recognize. With your problem, I do not see how to tell the good inputs (weakly perfect graphs) from the not-good inputs.
Gamow
CC BY-SA 3.0
2015-01-23T10:19:42.703Z
@Gerhard Indeed the class is very broadly defined. Ideas about improving the question, maybe a promise? If they happen to be NPC wouldn't constructing explicit subclass solve the problem (like the algebraic construction?. Don't claim this is true).
joro
CC BY-SA 3.0
2015-01-23T13:44:19.580Z
As was already mentioned in the MO thread, deciding $k$-colourability of weakly perfect graphs is polynomial time as $\chi(G)=\vartheta(G)$. The problem is whether one can efficiently find a colouring.
Emil Jeřábek
CC BY-SA 3.0
2015-01-23T13:46:08.763Z
@EmilJeřábek I think the reference on MO doesn't hold after the discussion, what is a reference for theta?
joro
CC BY-SA 3.0
2015-01-23T13:49:11.833Z
This is a well known fact. See e.g. https://en.wikipedia.org/wiki/Lov%C3%A1sz_number#Lov.C3.A1sz_.22sandwich_theorem.22 , where you can also find references.
Emil Jeřábek
CC BY-SA 3.0
2015-01-23T13:57:08.753Z
I have deleted my (faulty) answer. The main mistake was in the self reducibility part: I overlooked the case where by adding one edge the clique number and the chromatic number simultaneously go up by $+1$.
Gamow
CC BY-SA 3.0
2015-01-23T14:33:48.410Z
@Gerhard: Actually, I think that that would be OK (it would keep the graph weakly perfect). The problem was when adding an edge would preserve the clique number, but increase the chromatic number. Then the graph is no longer weakly perfect, hence the algorithm is free to say YES, in which case the reduction erroneously keeps the edge, and later comes to the false conclusion $\chi(G)>i$.
Emil Jeřábek
CC BY-SA 3.0
2015-01-23T14:51:52.980Z
@Gerhard Is depending on the running time rigorous? Computing say $f(G)=\chi(G)$ might depend only on the number of vertices for graphs in this class?
joro
CC BY-SA 3.0
2015-01-23T18:48:22.783Z
1) the question as stated is answered by @EmilJeřábek's comment above: deciding if a weakly perfect graph is $k$-colorable is in P by computing $\vartheta$. 2) If you had an efficient algorithm that finds an optimal coloring in weakly perfect graphs, couldn't you use it to find a coloring in any graph, as in Emil's MO comment? For each $k \in \{1, \ldots, n\}$, take the disjoint union of the input graph $G$ and a $k$-clique, run the algorithm for weakly perfect graphs and then take the best coloring over all the runs. For the optimal $k$ the disjoint union is weakly perfect, so you are done?
Sasho Nikolov
<graph-theory><complexity-classes>
Complexity of coloring in weakly perfect graphs?
joro
# Complexity of coloring in weakly perfect graphs?

(Asked by: username_0 on 2015-01-23)

A graph is [weakly perfect](http://dml.cz/bitstream/handle/10338.dmlcz/140801/CzechMathJ_60-2010-4_11.pdf) if the clique number equals the chromatic
number, i.e. $\omega(G)=\chi(G)$. Deciding membership is NP-complete
according to the paper.

Because of the inequality $\omega(G) \le \chi(G)$ a $k$-clique is certificate
that there isn't smaller than $k$ coloring.

> What is the complexity of deciding if a weakly perfect graph is
> $k$-colorable?

---

Appears to me it might not be NP-complete because the certificate
will involve co-NP.

Also it might not be in P since it will decide coloring graphs for which
the inequality happens "by chance" and possibly by adding disjoint
cliques might be improved.

Searching the web found algebraic constructions of weakly perfect.
In all papers coloring was polynomial via closed form.

Related to [this](https://mathoverflow.net/questions/194431/graph-classes-where-finding-explicit-coloring-have-certificate-that-it-is-minumu).

**Tags:** graph-theory, complexity-classes

> **Comments:**
> **username_1**: A standard assumption in complexity theory is that well-formed inputs are easy to recognize. With your problem, I do not see how to tell the good inputs (weakly perfect graphs) from the not-good inputs.  
> **username_0**: @Gerhard Indeed the class is very broadly defined. Ideas about improving the question, maybe a promise? If they happen to be NPC wouldn't constructing explicit subclass solve the problem (like the algebraic construction?. Don't claim this is true).  
> **username_2**: As was already mentioned in the MO thread, deciding $k$-colourability of weakly perfect graphs is polynomial time as $\chi(G)=\vartheta(G)$. The problem is whether one can efficiently find a colouring.  
> **username_0**: @EmilJeřábek I think the reference on MO doesn't hold after the discussion, what is a reference for theta?  
> **username_2**: This is a well known fact. See e.g. https://en.wikipedia.org/wiki/Lov%C3%A1sz_number#Lov.C3.A1sz_.22sandwich_theorem.22 , where you can also find references.  
> **username_1**: I have deleted my (faulty) answer. The main mistake was in the self reducibility part: I overlooked the case where by adding one edge the clique number and the chromatic number simultaneously go up by $+1$.  
> **username_2**: @Gerhard: Actually, I think that that would be OK (it would keep the graph weakly perfect). The problem was when adding an edge would preserve the clique number, but increase the chromatic number. Then the graph is no longer weakly perfect, hence the algorithm is free to say YES, in which case the reduction erroneously keeps the edge, and later comes to the false conclusion $\chi(G)>i$.  
> **username_0**: @Gerhard Is depending on the running time rigorous? Computing say $f(G)=\chi(G)$ might depend only on the number of vertices for graphs in this class?  
> **username_3**: 1) the question as stated is answered by @EmilJeřábek's comment above: deciding if a weakly perfect graph is $k$-colorable is in P by computing $\vartheta$. 2) If you had an efficient algorithm that finds an optimal coloring in weakly perfect graphs, couldn't you use it to find a coloring in any graph, as in Emil's MO comment? For each $k \in \{1, \ldots, n\}$, take the disjoint union of the input graph $G$ and a $k$-clique, run the algorithm for weakly perfect graphs and then take the best coloring over all the runs. For the optimal $k$ the disjoint union is weakly perfect, so you are done?  

---

## 0 answers

