如果我们知道图是 3 色的，我们可以在多项式时间内对图进行 3 色吗？
Can we 3-color a graph in polynomial time if we know the graph is 3-colorable?
我知道决定一个图是否可三色是 NP 难题。但我想知道，当我们得到一个有保证的 3 色图时，我们能否在多项式时间内对图进行 3 色着色？
我找到的大部分资源都在谈论决定一个图是否是 3 色的......我不确定我应该在 google 中输入哪些关键字以获得更好的搜索结果......所以我在这里。任何帮助将不胜感激。
我在网上搜索 this paper。它的作者证明了用 4 种颜色给 3 种可着色图着色是 NP 难的。该结果适用于有界度 3 色图。
自从您考虑了合适的 google 搜索表达式后，我的
how to 3-color a 3-colorable graph
我知道决定一个图是否可三色是 NP 难题。但我想知道，当我们得到一个有保证的 3 色图时，我们能否在多项式时间内对图进行 3 色着色？ 我找到的大部分资源都在谈论决定一个图是否是 3 色的......我不确定我应该在 google 中输入哪些关键字以获得更好的搜索结果......所以我在这里。任何帮助将不胜感激。
我在网上搜索 this paper。它的作者证明了用 4 种颜色给 3 种可着色图着色是 NP 难的。该结果适用于有界度 3 色图。
自从您考虑了合适的 google 搜索表达式后，我的
how to 3-color a 3-colorable graph