研究者情報

キーワード

辺着色問題

有限個の頂点とその間を結ぶ辺からなる図形をグラフと呼び、グラフ理論ではグラフの構造や組合せ的な性質を研究します。その中で辺着色問題は、辺に色を塗ったグラフの構造や性質を考える問題で、Ramsey理論もその中に含まれます。有名な四色定理は「平面に交差無く埋込み可能な３正則グラフは、彩色と呼ばれる３色からなる辺着色を持つ」と言い換えることができ、これまでも辺着色問題はとても活発に研究されてきました。

Bermond-Thomassen予想

辺に向きを与えたグラフを有向グラフと呼びます。Bermond-Thomassen予想は有向グラフのサイクル構造についての未解決問題です。有向グラフは辺着色グラフに一般化でき、Bermond-Thomassen予想も辺着色グラフ上の予想に言い換えることができます。最近その特別な場合の解決に成功したので、さらに一般な場合の解決を目指しています。

Gallaiの構造定理

ErdosとRadoはRamseyの定理を一般化したCanonical Ramsey定理を証明しました。一方Gallaiは３色で塗られた三角形を含まない辺着色された完全グラフの構造を決定しました。有向グラフは辺着色グラフの特別な場合で、これまで様々な結果が得られていますが、有向グラフの一般化でない辺着色グラフの構造は未解決問題です。現在その特徴づけに取り組んでいて、ようやくその一端が解明できてきました。