检查着色图所需的最少颜色数（2-正则图中的色数）

Question

我的任务是检查图形着色中使用的最少颜色数，即图形的色数。我的无向图是 2 正则图（每个顶点都是 2 度）。我找到了

的解决方案

(最大独立集数)/顶点数=颜色数 (色数)

https://imgur.com/a/ZtyP4v9 - 看起来如何

如你所见，如果结果是2，它可以是2色的；如果结果大于2，它可以是3色的。

但是我不知道如何在这样的图中找到最大独立集。

Answer 1

2-正则图只不过是不相交循环的并集。如果任何循环的长度为奇数，则色数为 3，否则为 2。就这么简单。你不需要算法。