【研究分野】数学一般(含確率論・統計数学)

【研究領域課題番号】24340021 (KAKENデータベースで見る）

【研究キーワード】

グラフ理論 / 極値問題 / 弦付きサイクル / シータグラフ / マッチング拡張性 / Hadwiger予想 / 禁止部分グラフ / グラフマイナー / 彩色問題 / 森グラフ / 国際情報交換 / アメリカ / 完全マッチング / 台湾 / タフネス / 国際研究者交流 / アメリカ:台湾

【研究成果の概要】

極値グラフ理論の問題は，グラフ H を固定するとき，与えられたグラフ G が H と同型な部分グラフを含むための辺数あるいは最小次数に関する最善の十分条件を求めることである．本研究では，因子問題，マイナー，部分グラフに関する問題を統一的な視点から俯瞰することにより，新たな問題提起を行い，展開研究を行った．とくに，森グラフの極値問題，弦付きサイクルやシータグラフを点素に見つける問題，マッチング拡張性などを重点的に扱った．また，グラフ理論の大きな未解決問題の一つであるHadwiger予想との関連において，グラフのρ彩色の概念を導入し，次数列に関するHadwiger予想の簡潔な証明を与えた．

【研究種目】基盤研究(B)

【研究期間】2012-04-01 - 2017-03-31

【配分額】9,880千円 (直接経費: 7,600千円、間接経費: 2,280千円)

【研究分野】数学一般(含確率論・統計数学)

【研究領域課題番号】20340023 (KAKENデータベースで見る）

【研究キーワード】

組合せ論 / グラフ / マイナー / 禁止マイナー / 禁止部分グラフ / 完全マッチング / クローフリーグラフ / タフネス / グラフ理論 / グラフマイナー / 閉曲面上への埋め込み / 全域木

【研究成果の概要】

与えられたグラフの部分グラフから,辺の縮約を繰り返して得られるグラフを,元のグラフのマイナーと呼ぶ.平面グラフなど重要なグラフの族はマイナーに関して閉じており,禁止マイナーによって特徴づけされる.これまでに知られていた平面グラフなどにおける閉路,全域木,因子に関する問題を,禁止マイナーの観点から拡張することを行った.とくに完全2部グラフをマイナーとして含まないグラフのタフネス,全域木に関する性質で顕著な成果が上がった.加えて,禁止部分グラフによる同種の問題にも成果があった。

【研究種目】基盤研究(B)

【研究期間】2008 - 2011

【配分額】6,240千円 (直接経費: 4,800千円、間接経費: 1,440千円)