グラフの閉曲面への埋め込みとその特徴付け

本年度は前年度に引き続き、閉曲面上の三角形分割グラフと四角形分割グラフ及びその周辺の研究を行った。研究は大きく分けて三つの方向に進展した。まず四角形分割から三角形分割への拡張に関して、「任意の四角形分割グラフに対し、各面に対角辺をうまく入れることにより、4-連結三角形分割グラフにできる」という主張を証明し、学術誌Graphs and Combinatoricsへの掲載が決定した。また前年度得られた偶三角形分割への拡張に関する結果は、学会誌SIAM Journal on Discrete Mathematicsへ投稿中である。次にその逆問題、任意の三角形分割グラフから2部的四角形分割グラフを探す問題において、偶三角形分割グラフの族に対して部分的結果を得ることができた。とくに射影平面上とトーラス上では完全解決することができ、その研究成果を8月の新潟の研究集会で発表した。三つ目は閉曲面上のグラフの彩色問題に関する、Grunbaum coloringと呼ばれる彩色の研究が進展した。局所平面グラフと呼ばれる、 5-頂点彩色が保証されたグラフの族の中で、 4-頂点彩色を持たないフィスク三角形分割グラフという興味深い研究対象がある。それにmonodromyという概念を用いることにより、「任意の局所平面的フィスク三角形分割グラフがGrunbaum coloringを持つこと」、及び「任意の局所平面的フィスク三角形分割グラフが1頂点を除けば4-頂点彩色可能であること」を示すことができた。これらの結果は閉曲面上のグラフの彩色分野における大きな予想である「Albertson予想」と「Robertson予想」の解決への足がかりとなる重要なものであり、12月に龍谷大学にて行われた応用数学合同研究集会にて、招待講演として発表した。また前年度得られた巡回的4-彩色に関する結果は、学会誌Journal of Graph Theoryへ投稿中である。

本年度は前年度に引き続き、閉曲面上の三角形分割グラフと四角形分割グラフ及びその周辺の研究を行った。研究は大きく分けて三つの方向に進展した。まず四角形分割から三角形分割への拡張に関して、「任意の四角形分割グラフに対し、各面に対角辺をうまく入れることにより、4-連結三角形分割グラフにできる」という主張を証明し、学術誌Graphs and Combinatoricsへの掲載が決定した。また前年度得られた偶三角形分割への拡張に関する結果は、学会誌SIAM Journal on Discrete Mathematicsへ投稿中である。次にその逆問題、任意の三角形分割グラフから2部的四角形分割グラフを探す問題において、偶三角形分割グラフの族に対して部分的結果を得ることができた。とくに射影平面上とトーラス上では完全解決することができ、その研究成果を8月の新潟の研究集会で発表した。三つ目は閉曲面上のグラフの彩色問題に関する、Grunbaum coloringと呼ばれる彩色の研究が進展した。局所平面グラフと呼ばれる、 5-頂点彩色が保証されたグラフの族の中で、 4-頂点彩色を持たないフィスク三角形分割グラフという興味深い研究対象がある。それにmonodromyという概念を用いることにより、「任意の局所平面的フィスク三角形分割グラフがGrunbaum coloringを持つこと」、及び「任意の局所平面的フィスク三角形分割グラフが1頂点を除けば4-頂点彩色可能であること」を示すことができた。これらの結果は閉曲面上のグラフの彩色分野における大きな予想である「Albertson予想」と「Robertson予想」の解決への足がかりとなる重要なものであり、12月に龍谷大学にて行われた応用数学合同研究集会にて、招待講演として発表した。また前年度得られた巡回的4-彩色に関する結果は、学会誌Journal of Graph Theoryへ投稿中である。