Graph coloring and completeness of NP
I am having trouble understanding the completeness of the NP graph coloration.
If I adopt a greedy coloring strategy ( http://en.wikipedia.org/wiki/Graph_coloring#Greedy_coloring ) with DFS, then I seem to be able to colorize the graphs optimally. Can anyone help me with a counter example?
To be clear, let all nodes be colored -1. Start color of node 1. Walk around the DSP by coloring each node with a minimum integer that has not yet been assigned to its neighbors. When would it not be optimal to color the graph?
source to share