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

Question

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

（最大独立集数）/顶点数=颜色数（色数）

https://imgur.com/a/ZtyP4v9 - 它的样子

如您所见，如果结果为 2，则可以是 2 色，如果结果大于 2，则可以是 3 色。

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

Answer 1

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