algorithm - 图着色和NP完整性

Question

我无法理解图形着色的 NP 完整性。

如果我假设使用 DFS 的贪婪着色策略（http://en.wikipedia.org/wiki/Graph_coloring#Greedy_coloring），那么我似乎能够以最佳方式为图形着色。谁能帮我举个反例？

为了清楚起见，让所有节点都被着色为-1。为起始节点着色 1. 继续进行 DFS 遍历，用尚未分配给其邻居的最小整数为每个节点着色。什么时候无法为图形优化着色？

Answer 1

DFS 贪婪着色在某些图表上肯定会失败。想出一个反例的方法是尝试写一个证明 DFS 将优化颜色。证明你不能开始工作的部分是提出反例的提示。