グラフ彩色のNP完全性を理解するのに苦労しています。
DFSで貪欲な彩色戦略（http://en.wikipedia.org/wiki/Graph_coloring#Greedy_coloring）を想定すると、グラフを最適に彩色できるようです。誰かが反例で私を助けてもらえますか？
明確にするために、すべてのノードを-1に色付けします。開始ノードに色を付ける1.隣接ノードにまだ割り当てられていない最小の整数ですべてのノードに色を付けるDFSトラバーサルを続行します。これがグラフの最適な色付けに失敗するのはいつですか？