Graph coloring doesn't have certificate that smaller coloring doesn't exist in general.

I am looking for graph classes where finding explicit coloring is not polynomial and have polynomially verifiable certificate that it is minimum.

Example of such class might be graphs for which the clique number equals the chromatic number, i.e. $\omega(G)=\chi(G)$ and finding coloring is not polynomial. Find both coloring and clique and the clique will be certificate that smaller coloring doesn't exist because of the inequality $\omega(G) \le \chi(G)$.

Are there nice characterizations of such graph classes (preferably by forbidden induced subgraphs)?

Paper defines such graphs "weakly perfect" and claims that deciding $\omega(G)=\chi(G)$ is NP-complete.

Near misses are perfect and cobipartite but there the problems are polynomial.

  • 1
    $\begingroup$ NP-complete = {in NP + NP-hard}, so your question doesn't make sense. Maybe there is a confusion? $\endgroup$ – Florent Foucaud Jan 21 '15 at 9:38
  • $\begingroup$ @FlorentFoucaud I don't think showing that k-coloring doesn't exist is NP-complete since you don't have certificate. Do you agree with this? NP-Complete requires certificate. Maybe I mean not in coNP? $\endgroup$ – joro Jan 21 '15 at 10:01
  • $\begingroup$ The revised question does not make sense either. No NP-complete problem is in coNP, unless NP =coNP. $\endgroup$ – Emil Jeřábek Jan 21 '15 at 10:25
  • $\begingroup$ @EmilJeřábek OK, thanks. Is there any hope in saving the question in case the other part makes sense? $\endgroup$ – joro Jan 21 '15 at 10:27
  • $\begingroup$ I honestly do not understand what you are after. Since you seem to be confused about basic definitions, it might help if you rewrite the question avoiding terms like NP-complete and NP-hard, and explicitly express it using reductions. $\endgroup$ – Emil Jeřábek Jan 21 '15 at 10:34

One possible answer is the class of all $3$-chromatic graphs. That is, suppose I tell you that your input graph $G$ is $3$-chromatic and I ask you to find an optimal colouring. Evidently, every $3$-colouring will be its own certificate of optimality. On the other hand, it turns out that knowing that your graph is $3$-chromatic does not help much in finding an optimal colouring. I believe the state of the art is a paper of Kawarabayashi and Thorup which finds a $O(n^{0.2038})$-colouring in polynomial time for input graphs that are $3$-colourable. For hardness results, it is NP-hard to find a $5$-colouring in polynomial-time even knowing that your input graph is $3$-colourable. In fact, assuming a version of the Unique Games Conjecture, it is NP-hard to find a $O(1)$-colouring in polynomial-time for $3$-colourable graphs.

  • $\begingroup$ Interesting. Isn't a simpler certificate the fact that it is not bipartite? $\endgroup$ – joro Jan 22 '15 at 8:40
  • $\begingroup$ @joro: In Tony Huynh's setting, our input universe is the set of 3-chromatic graphs, that is, we know they are all non-bipartite and 3-colorable. Therefore it only makes sense to have a certificate depending on the output coloring. $\endgroup$ – Florent Foucaud Jan 22 '15 at 9:03
  • $\begingroup$ @FlorentFoucaud Indeed, but this can be extended to all graphs for which 3-coloring is found without the promise. $\endgroup$ – joro Jan 22 '15 at 9:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.