我正在搜索图形着色算法，我找到了 algorithm ，作者是如何在多项式时间内运行的。 作者还给出了C++程序源码和演示程序。
可疑的是图是否可k着色的决策问题是NP完全的，因此在P=NP之前不应该存在多项式时间算法。
然而，作者并没有声称，该算法适用于所有图，他只是说，他还没有找到算法对哪个图不起作用。
因此，问题是:该算法是否真的适用于每个图，这意味着实际上 P=NP，或者存在它不适用于的某些图/图类？还是复杂度计算有误？
最佳答案
我想你还没有仔细阅读摘要。
作者提出了一种算法，可以找到 m -图表的着色，对于一些m小于布鲁克斯定理施加的限制:https://en.wikipedia.org/wiki/Brooks '_定理
(这是旧的，并指出 chi < delta + 1 正如作者在第二句中所说的那样。)
作者知道P vs NP 问题。这篇论文并没有声称要解决这个问题，他只是说:
For all known examples of graphs, the algorithm finds a proper m-coloring of the vertices of the graph G for m equal to the chromatic number χ(G)
然后他问，
In view of the importance of the P versus NP question, we ask: does there exist a graph G for which this algorithm cannot find a proper m-coloring of the vertices of G with m equal to the chromatic number χ(G)?
强调原文 (!)
所以它并没有声称要解决 P vs NP，它只是作为一个学术研究问题，他们问“任何人都可以举出一个这个算法无法达到色数的例子”，这可能对他们出于数学目的。该算法实际上不太可能实现所有图形的色数。 (尽管从科学上讲，它是否起作用尚不得而知。)
关于algorithm - 我在网上找到了图形着色的多项式时间算法，可能证明P=NP，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/32464175/