平面图G，用大O表示法寻找B的m大小的上界

Question

设A是平面图G的顶点集合，B是最小的颜色集合，使得每个顶点可以分配给R中的颜色，并且没有两个相邻的颜色被分配给相同的颜色，寻找尺寸的上限具有大O符号的B的m。界限应尽可能紧。

答案是O（2 ^ n）吗？我不知道。我对这类任务不太熟悉，并想知道我将在哪里开始解决这样的任务？我粗略地阅读了计算几何，数据结构和算法，GIS - A Computing Perspective。但我无法理解它。任何输入都表示赞赏。谢谢。

Answer 1

正如我发现的那样，你想要最小数量的颜色用于平面图顶点着色。有一个叫做Four Color Theorem的定理。它说所有平面图都可以用4种颜色着色。

此外，你也可以检查Five Color Theorem。因此|B| = O(1)与平面图的顶点数无关。