我知道图形着色是一个 NP 完全问题。我想知道是否添加对可以具有给定颜色的顶点数量的限制会使问题更简单？我似乎找不到任何算法可以做到这一点。例如，如果我有一个图形，我想说“这个图形的最小着色是什么，使得每种颜色最多有 3 个顶点”，或者如果它简化了问题“有没有办法用这个图形着色4种颜色，每种颜色最多有3个顶点”？
谢谢！
问问题
598 次
2 回答
2
通过对原始图着色问题的简单简化，这个问题仍然是 NP 完全的：具有 n 个节点的图是 k 可着色的，当且仅当该图可以用 k 种颜色着色并且没有颜色分配给超过 n 个节点。换句话说，您要解决的问题的一般版本将图形着色作为一种特殊情况，因此它仍然是 NP 难的。
希望这可以帮助！
于 2013-04-12T17:44:15.510 回答
1
我会说，在存在k 着色的限制的情况下寻找图的色数可以很容易地添加到基于 DSATUR 的精确算法[Randall-Brown 72] [San Segundo 11]并在一个顶点时修剪搜索空间必须分配颜色k。无论如何，问题仍然存在于 NP 中。
于 2014-07-24T11:06:50.410 回答