無向グラフの色付け

Question

エッジの数と色の値を持つ無向グラフが与えられeますm。したがって、m隣接する2つの頂点が同じ色になっていないという条件で、グラフを異なる色で色付けできるかどうかを確認する必要があります。

頂点ごとに、頂点の次数が<のm場合、グラフにm色を付けることができると思います。

いずれかの頂点で次数が> =のm場合、グラフをm色で着色することはできません。

上記のアプローチを使用して、M-カラーリンググラフを解決しようとしましたが、機能しませんでした。

上記のアプローチが機能しない理由を誰かに教えてもらえますか？

与えられたテストケースの1つに疑問がありましたm= 3、頂点の数= 4、エッジ=eここでエッジは4-> 3、4-> 2、1-> 4、3-> 2、1-> 2 。

上記の無向グラフを3色で着色できると言っています。どうしてそれが可能でしょうか？頂点4の次数は3なので、隣接する頂点の数は3です。頂点4自体を含めると、隣接する頂点は4つあります。これらの4つの隣接する頂点を3色だけでどのように着色できますか？不可能だと思います。私が間違った考えをしているなら、私に知らせてください。

質問や質問の仕方に問題がある場合は、以下にコメントしてください。参考になります。

Answer 1

ノードの2つの隣接ノードは、同じ色を持つことができます（例：グラフ）

1----2
|    |
|    |
4----3

奇数の頂点を色1で、偶数の頂点を色2で色付けできるため、は2色になります。各頂点vについて、vの隣接する頂点は同じ色であり、vの色とは異なります。したがって、違反はありません。

Answer 2

の投稿から https://stackoverflow.com/a/63760170/14194633頂点の次数はグラフ彩色とは何の関係もないことを知りました。なぜなら、色付けでは、隣接する2つの頂点が同じ色にならないように色付けする必要があるからです。

質問に投稿した例から、m = 3の場合、頂点の次数4は3です。私のアプローチでは、頂点4自体を含めると、頂点4の次数が3なので、これらに色を付ける必要があります。隣接する4つの頂点で、4つの頂点をm3色だけで着色することは不可能だと思いました。しかし、それは真実ではありません。

頂点の次数4 >= m（m = 3の場合）でも、グラフを3色で着色できます。

ここで重要なのは、頂点の次数をチェックすることではなく、頂点に色を適用して、隣接する頂点が同じ色であるかどうかをチェックすることです。