Why Is vertex coloring NP-hard?

Question

I am reading up on vertex coloring algorithm. I see documents explaining how the problem can be solved using BFS (implying the problem can be solved in O(|V|+|E|). But I also see it mentioned that this is an NP-hard problem.

How do these two fit together? Could you please throw some light?

Here is the algorithm I came across, which looked like a general-case polynomial solution to me:

Have each color identified by a number. Start with a node and assign it the color with least number. Visit each of its neighbour using BFS. While visiting a node, check the color of each of its neighbours and assign the color with least number which is not assigned to any of its neighbours.

It is told that BFS approach works only for 2 colors. I am uable to see why the above technique wont work for more than 2 colors

Answer 1

Normally, when I think of bread-first search (BFS), I think of it as applying to trees, but vertex coloring is a graph problem, not a tree problem. I suppose you could apply BFS to a graph by adopting the rule that all nodes adjacent to the current one are labeled before moving to a different node.

First, look at a basic example of how simple labeling using lowest-number ordering (called sequential ordering) does not work:

If we label the nodes in clockwise order (A to J) we end up with a 4-coloring, when in fact this graph has a 2-coloring. Now, your rule, prioritizing labeling adjacent nodes will work, because it is a two-coloring. But, there are 3-colorings for which your rule will not work, for example:

In this example we choose A as the root of the "tree", and do its children first, B and C. Then, we choose child B, because it is lower alphabetic order than C, and do all of B's children. We end up with a 4-coloring, when in fact the graph can be 3-colored.

Answer 2

A special case of Vertex Coloring, or an approximation can be achieved using BFS. The general problem is NP-Complete, and BFS fails to solve every case of it. I would love to try and provide a counter-example, but your description of the algorithm is lacking - the coloring strategy is not clear.

For example, a simple coloring achieveable by BFS is c(v) = d(source,v) (in here c(v) is the color, d(source,v) is the distance from the source to the vertex, as retrieved by BFS)).
It is easy to see this is not optimal for A--B--C--D, where you can color it with 2 colors, but this solution uses 4 colors.

Answer 3

The algorithm using BFS solves a relaxed case of vertex coloring problem where the number of colors are not fixed and it can work sometimes as a approximation solution from general NP complete problem which to color a graph using k colors or finding the minimum set of colors which can be used to color the graph