I am new to the complexity theory and I am trying to understand what would be the complexity of the following problem: "Is a graph AT LEAST $k$-colorable?"

Whether a graph is $k$-colorable is clearly a NPC problem and is explained by reduction to 3-SAT.

However, I am not sure to which complexity class belongs the modified problem I have stated. Does it belong to NP as well? My guess is that we would be able to check it with a polynomial certificate (any $\geq k$ coloring of the graph).

And then the problem "Is a graph AT MOST $k$-colorable?" would be its complement in co-NP unless NP=co-NP?

  • $\begingroup$ Could you give an example of a graph that is not "at least 3-colorable"? $\endgroup$ Sep 7, 2020 at 21:23
  • $\begingroup$ Tom: probably any graph with 0, 1, or 2 nodes. $\endgroup$
    – gnasher729
    Sep 8, 2020 at 21:29

1 Answer 1


Well, all graphs are colorable with $\geq k$ colors: Assign each vertex a different color (and leave the other color classes empty if $k$ is larger than the number of vertices of the given graph).

As for the complement of this problem, note that you did not correctly invert the definition of the problem: A problem $L$ is, after all, merely a set of strings over some finite alphabet $\Sigma$ representing some objects with some property. Its complement is then the set $\Sigma^\ast \setminus L$ or the set of all strings not representing an object with the property. If we recall the argument above, we find that the complement of your problem is hence the set of all strings not representing graphs (under that fixed encoding scheme) rather than the one you claimed. This problem (as the first one), is in $\mathsf P$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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