How to understand the reduction from 3-Coloring problem to general $k$-Coloring problem?

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?

3 Answers

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.

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.

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.

• "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$. Jan 1, 2013 at 15:01
• @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? Jan 1, 2013 at 18:17
• Yes, $k$ is constant while $n$ depends on the size of the graph. Jan 1, 2013 at 23:02