Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

3-Coloring problem can be proved NP-Complete making use of the reduction from 3SAT Graph Coloring (from 3SAT). As a consequence, 4-Coloring problem is NP-Complete using the reduction from 3-Coloring:

Reduction from 3-Coloring instance: adding an extra vertex to the graph of 3-Coloring problem, and making it adjacent to all the original vertices.

Following the same reasoning, 5-Coloring, 6-Coloring, and even general $k$-Coloring problem can be proved NP-Complete easily. However, my problem comes out with the underlying mathematical induction:

My Problem: What if the induction goes on to $n-1$-Coloring and $n$-Coloring problem, where $n$ is the number of vertices in the graph? I certainly know that $n$-Coloring problem can be solved trivially. So, is there something wrong with the reasoning? How to understand the reduction from 3-Coloring problem to the general $k$-Coloring one?

share|improve this question

3 Answers 3

up vote 6 down vote accepted

The $k$-coloring problem is usually defined only for constant $k$, so $n$-coloring doesn't make sense. For every constant $k \geq 3$, the reduction you mention works. By adding a superconstant number of vertices you can show, for example, that $(n/2+3)$-coloring is NP-complete.

share|improve this answer

Your apparent contradiction comes from abusing the notation "$n$": its meaning changes as you move through the question.

When you say that $n$-colouring is trivial, what you actually mean is that it's trivial to colour any graph $G$ with $|V(G)|$ colours. But the $n$-colourability problem for any constant $n$ is the problem of determining whether an arbitrary input graph, with any number of vertices, has a proper $n$-colouring.

The chain of reductions from $3$-colourability to $n$-colourability adds $n-3$ vertices to the graph. This means that the only way you could end up with a trivial instance of the $n$-colourability problem is if your original input to the $3$-colourability problem had $3$ or fewer vertices – such an instance was already trivially $3$-colourable.

By the way, there's no need to use induction to prove that $k$-colourability is NP-complete for every $k\geq 3$ because it's easy to compose the sequence of reductions that would appear in the induction. A graph $G$ is $3$-colourable if, and only if, the graph $G'$ is $k$-colourable, where $G'$ is the disjoint union of $G$ and a copy of K_{k-3}$, plus all possible edges between the two parts.

share|improve this answer

The $k$-coloring problem is to color any graph. You can certainly find graphs for which $k$-coloring is trivial as well as formulas for which SAT is trivial or etc. This does not impact the complexity of the problems in general though.

share|improve this answer
1  
"Graphs for which $k$-coloring is trivial... formulas for which SAT is trivial" - every single graph is trivial to $k$-color, every single formula to determine its satisfiability, since the solution can be hardcoded. However, SAT and 3-colorability are NP-hard. In contrast, $n$-colorability has a polytime algorithm. The OP was worried that this contradicted a proof that $k$-colorability is NP-hard for every $k$. –  Yuval Filmus Jan 1 '13 at 15:01
1  
@YuvalFilmus, I suppose I meant classes of graphs or formulas for which the problems are easier. I'm confused though. Are k-coloring and n-coloring different problems somehow? –  Karolis Juodelė Jan 1 '13 at 18:17
    
Yes, $k$ is constant while $n$ depends on the size of the graph. –  Yuval Filmus Jan 1 '13 at 23:02

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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