グラフ理論の問題について

質問

Gをn個の頂点とM本の辺を含む、以下の条件を満たすグラフとします。

このグラフの全ての辺をk通りの異なる色に彩色したとき、そのうち任意のm個の異なる色が選ばれたとしても残りのk-m色のみで塗られた辺によって出来た部分グラフが連結であるような彩色の仕方が存在する。

ここでk,n,mをパラメーターとした時、「最小の」Mの値を求めたいのですが、m=1の時の解しか得られませんでした。どのようなグラフ理論的なテクニックを用いてこの問題を解くべきなのでしょうか？この種の問題は一般的にグラフ彩色の問題として分類されるのでしょうか？なにか一般解を得るためのヒントや手助けとなりそうなアイディアや論文などありましたらお教え願いたいです。

回答No.1

stomachman · ベストアンサー

k＞m≧0, n≧1の場合の問題の条件をC(G,n,M,k,m)、これを満たす最小のMを
　　Min(n,k,m) = min{ M | C(G,n,M,k,m) }
とでもしましょうか。とりあえず、自明な関係がいくつか存在しそうです。
　　Min(n,k+1,m) ＜ Min(n,k,m)
　　Min(n,k,m)+m ＜ Min(n+1,k,m)
のような。まずはそういうのを整理しておいて、それから問題の本質を探ってみるかな。