We know that 5COLOR problem is NP-complete. careful 5COLOR problem is that: Given a graph G, can we color each vertex with an integer from the set {0,1,2,3,4}, so that for each edge, the colors of the two endpoints differ by exactly 1 modulo 5.

Can we show that careful 5COLOR is in NP?


2 Answers 2


The way you show that anything is in NP is pretty much the same. It always has the form "The nondeterministic Turing machine should guess a solution, and then it can check (in polynomial time) that the solution is correct."

In this case it looks like this: "The nondeterministic Turing machine should guess a coloring of the vertices of $G$, and then check in polynomial time that for each edge of $G$, its two endpoints have colors that satisfy the given condition."

The important details that you must establish are:

  1. Can the NTM really construct the coloring in polynomial time? In this case yes, since the coloring is just an assignment of integers to the vertices, and the number of vertices is bounded by a polynomial in the size of $G$.
  2. Can the NTM really check in polynomial time whether the condition is satisfied for every pair of vertices that are connected by an edge? Yes, because each check takes constant time, and the number of checks is equal to the number of edges in $G$, which is bounded by a polynomial in the size of $G$.
  • $\begingroup$ Thanks for your answering. If I understand it right, what you said is that NTM can construct and check a coloring in polynomial time, so that this must be a NP problem, right? FYI: What I want to ask is just whether this is a NP problem or not. $\endgroup$
    – babysnow
    Commented Dec 17, 2012 at 3:31
  • $\begingroup$ Yes, that is what I said. $\endgroup$
    – MJD
    Commented Dec 17, 2012 at 3:39

Alternatively, if we take the definition of NP as the class of problems that can be verified in polynomial time, we can see that Careful 5-COL is in NP because there is a deterministic Turing machine that can check an answer in polynomial time.

In particular, given an instance $G$, we can take a certificate that $G$ is carefully 5-colorable as a function $f:V(G)\rightarrow \{0,\ldots,4\}$. Given this function, we can take each edge $uv$, and check that $f(v)-f(u) \equiv 1 (5)$. We only have to look at each edge once, so the algorithm to check is $O(|E|)$ (even if we're nasty about how $f$ is encoded, it's still something like $O(|E|\times|V|)$).


You must log in to answer this question.

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