algorithm - グラフを着色するのに必要な最小色数を確認します (2-正則グラフの彩色数)

Question

私の仕事は、グラフの彩色に使用される色の最小数を確認することです。これは単にグラフの色数です。私の無向グラフは 2-regular (各頂点は 2 度) です。私はその解決策を見つけました

(最大独立集合数)/頂点数=色数(彩色数)

https://imgur.com/a/ZtyP4v9 - どのように見えるか

ご覧のとおり、結果が 2 の場合は 2 色になり、結果が 2 より大きい場合は 3 色になります。

しかし、そのようなグラフで最大の独立セットを見つける方法がわかりません。

Answer 1

2-regular グラフは、互いに素なサイクルの和集合にすぎません。いずれかのサイクルの長さが奇数の場合、彩色数は 3 で、そうでない場合は 2 です。それはとても簡単です。これにはアルゴリズムは必要ありません。