algorithm - 为图表着色

Question

我在论坛上看到了这个问题：http ://www.geeksforgeeks.org/archives/19042

给定一个无向图和一个数 m，确定该图是否最多可以用 m 种颜色着色，使得图中没有两个相邻的顶点用相同的颜色着色。

我想知道您是否可以将顶点数与 m 的顶点数进行比较，而不是尝试找到特定的解决方案？

我错过了什么？

Answer 1

即使顶点 ( |V|) 的数量大于，也可能存在着色m。

例如，在二分图中- any 都有着色m>=2，而不管顶点的数量。

然而，在一个派系中，唯一可行的颜色需要m >= |V|

所以：

我想知道您是否可以将顶点数与 m 的顶点数进行比较，而不是尝试找到特定的解决方案？

如果m > = |V|- 有一个解决方案，但是，如果m < |V|- 我们什么也不能推导出来。反正可能会有答案。

奖励：对于一般情况，图形着色是经典的NP 完全问题之一 - 意思是 - 没有已知的多项式解决方案，如果可以找到 - 我们可以推导出P = NP