疎なグラフに対する極値グラフ理論の展開
【研究分野】数学基礎・応用数学
【研究キーワード】
グラフ理論 / 極値問題 / 疎グラフ / マッチング / サイクル / 辺彩色部分グラフ / マッチング拡張性 / 離散数学 / 組合せ論 / 1-平面グラフ
【研究成果の概要】
極値グラフ理論の問題は，グラフが特定の部分構造や性質を持つための条件として，そのグラフの辺数や最小次数に関する最善の十分条件を求める問題である。本研究では，グラフの辺数が頂点数の2乗オーダーにならないようなグラフ，いわゆる疎グラフにおける極値問題に着目し，従来の極値グラフ理論とは一線を画した研究を行った。とくに，森グラフの極値問題の展開，マッチング拡張性，グラフに含まれるサイクルの長さなどにおいて，これまでの極値問題の視点とは異なる立場からの成果を得た。また，1-平面グラフでの極値問題や，辺着色グラフに彩色部分グラフを見つける問題など，新たな極値問題への展開研究も行った。
【研究の社会的意義】
極値グラフ理論の典型的な定理では，辺数が頂点数の2乗オーダーであるグラフ（密なグラフと呼ばれる）が極値グラフとなる。密なグラフに対する極値問題に対しては，Regularity Lemmaとその応用であるBlow-up Lemmaが強力な道具となることが知られている。それに対して，辺数が頂点数の2乗オーダーに満たない疎グラフに対する極値問題は，まだ一般論が構築されておらず，多くの未解決問題が残る。疎なグラフでの極値問題に関する本研究成果は，そのような未解決問題を一つずつ解決していくステップではあるが，ゆくゆくは一般論の構築につながることが期待され，学術的意義は大きい。
【研究代表者】