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?
DFS hard coloring will certainly fail on some charts. A way to come up with a counterexample is to try and write a proof that DFS will color optimally. Part of the proof that you can't get to work is hinting at coming up with a counterexample.