algorithm - 图形的3色(多项式时间)？

我们能在多项式时间内用3种颜色给图上色吗？我读到用2
颜色很简单，但是用3种不同的颜色（没有两个顶点有
同样的颜色）是NP难的。但是，我想知道是否有一个魔盒对“A”说“是”
图在多项式时间内是3-可着色的。如果它说“是”，它将如何解决
多项式时间有什么想法吗？

最佳答案

向图形中添加3个名为红/绿/蓝的新顶点，每个顶点连接到另2个顶点，但没有其他顶点。
对于图中的每个顶点：
如果生成的图是3可着色的，则将顶点连接到红色
否则，如果生成的图是3可着色的，则将顶点连接到绿色
否则，将顶点连接到蓝色（通过构造，生成的图形必须是3可着色的）
在这个过程的最后，你将为每个顶点确定一种颜色。
这是O（n*魔法），魔法是你魔盒的复杂性。

关于algorithm - 图形的3色(多项式时间)？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/26851829/