我正在搜索图形着色算法，并且我找到了algorithm，作者陈述的算法是在多项式时间内运行的。作者还给出了C++程序源代码和演示程序。
可疑之处在于，图是否为 k 可着色的决策问题是 NP 完全的，因此在 P=NP 之前不应该存在多项式时间算法。
但是，作者并没有声称该算法适用于所有图，他只是说，他没有找到任何算法不适用于该图。
所以，问题是：该算法是否真的适用于每个图，这实际上意味着 P = NP，还是存在某些不适用的图/图类？或者也许只是复杂性计算中的错误？
问问题
664 次
1 回答
2
我认为你没有仔细阅读摘要。
作者提出了一种算法，该算法可以找到m图形的着色，对于一些m小于布鲁克斯定理施加的限制：https ://en.wikipedia.org/wiki/Brooks'_theorem
（这是旧的，chi < delta + 1正如作者在第二句话中所说的那样。）
作者知道P vs NP问题。这篇论文并没有声称可以解决这个问题，他只是说：
对于所有已知的图示例，该算法为图 G 的顶点找到适当的 m 着色，因为 m 等于色数 χ(G)
然后他问，
鉴于 P 与 NP 问题的重要性，我们问：是否存在一个图 G，该算法无法找到 G 的顶点的适当 m 着色，其中 m 等于色数 χ(G)？
强调原创（！）
因此，它并没有声称要解决 P 与 NP，只是作为学术研究的问题，他们问“任何人都可以提出一个该算法未能达到色数的示例”，这可能对他们的数学有启发性目的。该算法实际上不太可能实现所有图的色数。（尽管从科学上讲，它是否存在是未知的。）
于 2015-09-08T18:00:13.623 回答