2
$\begingroup$

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.

Improve this question
$\endgroup$
20
  • 1
    $\begingroup$ NP-complete = {in NP + NP-hard}, so your question doesn't make sense. Maybe there is a confusion? $\endgroup$
    – Florent Foucaud
    Commented Jan 21, 2015 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
    Commented Jan 21, 2015 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
    Commented Jan 21, 2015 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
    Commented Jan 21, 2015 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
    Commented Jan 21, 2015 at 10:34

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Interesting. Isn't a simpler certificate the fact that it is not bipartite? $\endgroup$
    – joro
    Commented Jan 22, 2015 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
    Commented Jan 22, 2015 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
    Commented Jan 22, 2015 at 9:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .