着色图

-2

给定一个无向图和数字m，确定该图可以至多M的颜色使得图的两个相邻顶点着色着色相同的颜色。

我想知道你是否可以将顶点的数量与m，比较，而不是试图找到一个特定的解决方案？

我错过了什么？

2012-05-10 Manish V

即使顶点数（|V|）大于m，也可能存在着色。

例如，在bipartite graph - 任何m>=2都有着色，无论顶点的数量如何。

在clique然而，唯一可行的色素需要m >= |V|

所以：

我想知道，而不是试图找到，如果你能顶点数量只是比较的m ，一个特定的解

如果m > = |V| - 有一个解决方案，但是，如果m < |V| - 我们可以得到什么。无论如何可能有答案。

加成：图着色，对于一般情况下是古典NP-Complete问题之一 - 即 - 存在用于其没有已知的多项式的解决方案，并且如果一个可以找到 - 我们可以推导出P = NP

2012-05-10 11:37:25 amit

回答