6
$\begingroup$

A graph is weakly perfect 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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Gamow Jan 23 '15 at 9:34
  • $\begingroup$ @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). $\endgroup$ – joro Jan 23 '15 at 10:19
  • 3
    $\begingroup$ 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. $\endgroup$ – Emil Jeřábek Jan 23 '15 at 13:44
  • $\begingroup$ @EmilJeřábek I think the reference on MO doesn't hold after the discussion, what is a reference for theta? $\endgroup$ – joro Jan 23 '15 at 13:46
  • 1
    $\begingroup$ 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? $\endgroup$ – Sasho Nikolov Jan 23 '15 at 18:48

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.