本地图被三角化时，4 色问题是否有所缓解？
出于调试目的，我想用尽可能少的颜色为凸 3D 多面体表面的三角形着色(这样我就有很多清晰可辨的颜色来为特别感兴趣的三角形着色)。
4 色定理指出 4 种颜色足以做到这一点，但我希望在表面被三角化的附加条件下，会有比一般情况更简单、更有效的算法。
此外，在我的几个划痕示例中，我总是可以使用 3 种颜色。
最佳答案
如果您考虑四面体，则无法仅用 3 种颜色为其面/三角形着色。因此，维数为 3 的三角凸多胞形的面可以用 3 种颜色着色是不正确的。但这恰好是唯一的反例!
事实上，您要着色的图形是三次(在每个面上放置一个顶点，并将其连接到三个相邻的面)，即每个顶点的度数为 3，并且它是也已连接。因此，通过 Brooks' theorem ，每个K_4不同的立方连通图最多可以用3种颜色着色。
编辑:
我在第一次阅读时没有注意到您也在寻找一种算法。我所知道的关于 Brooks 定理的证明是建设性的，因此我们有一个算法可以解决您的问题。
使用 Steinitz's theorem在多面体的对偶图上，我们得到我们想要着色的图总是 3-连通的。这并不是真正需要的，因为证明适用于另一种情况，但这是更简单的情况，所以让我坚持使用 3-connected 情况，因为这是你的情况。
取任意三个顶点 v_1、v_2、v_n 使得 v_n 与其他两个相邻，但是 v_1 和 v_2 是不相邻的(对于完整的图，这样的三元组不存在)。使用该图是 3 连通的，很明显，如果我们删除 v_1 和 v_2，生成的图仍然是连通的。
将剩余的顶点排列成 v_3, v_4, ..., v_n 序列，这样对于每个 v_i 存在 j> i 使得 v_i 和 v_j 相邻(这就像构造一个跨越Prim 算法中的树从 v_n 开始)。将v_1、v_2放在序列的开头，从而得到v_1、v_2、v_3, ..., v_n。
v_1 和 v_2 使用颜色 1(这是有效的，因为它们不相邻)。现在按顺序为序列的其余部分贪婪地着色，即为每个顶点分配第一个有效颜色(第一个未分配给已经着色的邻居)。对于除 v_n 之外的每个顶点，我们都有一个“右邻”，因此使用的颜色不超过 3 种。对于 v_n 它也有效，因为 v_1 和 v_2 的颜色都是 1。现在我们有图的 3 色，算法是线性的在图表的大小。
关于algorithm - 本地图被三角剖分时，4 色定理是否容易解决？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/26699020/