Clever Geek Handbook

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?

0


source to share


1 answer


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.



0


source






More articles:


All Articles