8
$\begingroup$

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?

$\endgroup$

3 Answers 3

7
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

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

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.