曲面上のグラフのマイナー関係とその構造に関する研究

1937年,K.Wagnerによって5頂点からなる完全グラフK5をマイナーに持つグラフの構造が特徴付けられたが,6頂点以上の完全グラフに関しては何も知られていない状況であった.ところが,2003年にB.Moharたちは,「グラフが閉曲面に埋め込める」という位相幾何学的な条件を付加することにより,「射影平面上の5-連結3-representativeグラフはK6をマイナーに持つ」という定理を証明した.この結果により,K6をマイナーに持つためのある程度意味のあるグラフ構造が記述されたが,まだ十分条件を与えるに留まっていた.そこで本研究では,曲面上のグラフを「三角形分割(各面が三角形であるような曲面上の単純グラフ)」に限定した.B.Moharたちの定理よりも条件は強くなっているが,射影平面,トーラス,ダブルトーラス,クラインの壷,種数3の向き付け不可能な閉曲面上の三角形分割がK6をマイナーに持つための必要十分条件を示している.これらの結果を皮切りに,完全グラフをマイナーに持つ曲面上のグラフ構造とその関連についての研究を行った.今年度の研究結果の一つとして,種数4の向き付け不可能な閉曲面上の三角形分割がK6をマイナーに持つための必要十分条件を示した.この結果から「種数4の向き付け不可能な閉曲面の全ての5-連結三角形分割と全ての4-representative三角形分割はK6をマイナーに持つ」という系を得られた.また,その他の閉曲面上のグラフの研究として,四角形分割から偶三角形分割への拡張可能性についていくつかの結果が得られた.

1937年,K.Wagnerによって5頂点からなる完全グラフK5をマイナーに持つグラフの構造が特徴付けられたが,6頂点以上の完全グラフに関しては何も知られていない状況であった.ところが,2003年にB.Moharたちは,「グラフが閉曲面に埋め込める」という位相幾何学的な条件を付加することにより,「射影平面上の5-連結3-representativeグラフはK6をマイナーに持つ」という定理を証明した.この結果により,K6をマイナーに持つためのある程度意味のあるグラフ構造が記述されたが,まだ十分条件を与えるに留まっていた.そこで本研究では,曲面上のグラフを「三角形分割(各面が三角形であるような曲面上の単純グラフ)」に限定した.B.Moharたちの定理よりも条件は強くなっているが,射影平面,トーラス,ダブルトーラス,クラインの壷,種数3の向き付け不可能な閉曲面上の三角形分割がK6をマイナーに持つための必要十分条件を示している.これらの結果を皮切りに,完全グラフをマイナーに持つ曲面上のグラフ構造とその関連についての研究を行った.今年度の研究結果の一つとして,種数4の向き付け不可能な閉曲面上の三角形分割がK6をマイナーに持つための必要十分条件を示した.この結果から「種数4の向き付け不可能な閉曲面の全ての5-連結三角形分割と全ての4-representative三角形分割はK6をマイナーに持つ」という系を得られた.また,その他の閉曲面上のグラフの研究として,四角形分割から偶三角形分割への拡張可能性についていくつかの結果が得られた.