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?

Thanks for any suggestions.

share|improve this question

2 Answers 2

up vote 4 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

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.