graph coloring and NP completeness

Question

I am having trouble understanding the NP completeness of graph coloring.

If I assume a greedy coloring strategy (http://en.wikipedia.org/wiki/Graph_coloring#Greedy_coloring) with DFS, then I seem to be able to color graphs optimally. Could anyone help me with a counter example?

To be clear, let all nodes be colored -1. Color the start node 1. Proceed in a DFS traversal coloring every node with the minimum integer that is not already assigned to its neighbors. When would this fail to optimally color the graph?

Answer 1

DFS greedy coloring will certainly fail on some graphs. The way to come up with a counterexample is to try to write a proof that DFS will color optimally. The part of the proof that you can't quite get to work is the hint for coming up with a counterexample.