图形的3色（多项式时间）？

Question

我们可以在多项式时间内为图形着色3种颜色吗？我读到用2为图表着色颜色很容易，但是可以用3种不同的颜色给图形着色（没有两个顶点具有相同的颜色）是np硬的。但是，我想知道是否有一个魔术盒对“ A”说“是”图在多项式时间内是3色的？”。如果回答“是”，它将如何解决？多项式时间？有任何想法吗 ？

Answer 1

向您的图形添加3个新顶点，称为红色/绿色/蓝色，每个顶点与其他2个顶点相连，但仅此而已。

然后为图形中的每个顶点：

1. 如果结果图为3色，则将顶点连接为红色
2. 否则，如果结果图形为3色，则将顶点连接到绿色
3. 否则，将顶点连接到蓝色（通过构建，结果图必须为3色）

在此过程结束时，您将为每个顶点标识一种颜色。

这是O（N * magic），其中魔术是魔术盒的复杂性。

Answer 2

因此，从技术上讲，您想要将NP-Hard问题转换为NP-Complete问题。由于颜色分配是组合检查，因此您应该将图形重构为SAT。一旦获得了SAT，您就可以在P时间内解决它。因此，是的，您的问题确实具有多项式时间解。