グラフの因子，マイナー，部分グラフに関する極値問題の総合的研究
【研究分野】数学一般(含確率論・統計数学)
【研究キーワード】
グラフ理論 / 極値問題 / 弦付きサイクル / シータグラフ / マッチング拡張性 / Hadwiger予想 / 禁止部分グラフ / グラフマイナー / 彩色問題 / 森グラフ / 国際情報交換 / アメリカ / 完全マッチング / 台湾 / タフネス / 国際研究者交流 / アメリカ:台湾
【研究成果の概要】
極値グラフ理論の問題は，グラフ H を固定するとき，与えられたグラフ G が H と同型な部分グラフを含むための辺数あるいは最小次数に関する最善の十分条件を求めることである．本研究では，因子問題，マイナー，部分グラフに関する問題を統一的な視点から俯瞰することにより，新たな問題提起を行い，展開研究を行った．とくに，森グラフの極値問題，弦付きサイクルやシータグラフを点素に見つける問題，マッチング拡張性などを重点的に扱った．また，グラフ理論の大きな未解決問題の一つであるHadwiger予想との関連において，グラフのρ彩色の概念を導入し，次数列に関するHadwiger予想の簡潔な証明を与えた．
【研究代表者】
【研究分担者】 |
| 藤沢 潤 | 慶應義塾大学 | 商学部 | 准教授 | (Kakenデータベース) |
| 田村 明久 | 慶應義塾大学 | 理工学部 | 教授 | (Kakenデータベース) |
| 石井 一平 | 慶應義塾大学 | 理工学部 | 非常勤講師 | (Kakenデータベース) |
| 小田 芳彰 | 慶應義塾大学 | 理工学部 | 准教授 | (Kakenデータベース) |
|
【研究連携者】 |
| 山下 登茂紀 | 近畿大学 | 理工学部 | 准教授 | (Kakenデータベース) |
|
【研究協力者】 |
| 榎本 彦衛 | 元広島大学 | 大学院 | 教授 |
| 小関 健太 | 国立情報学研究所 | 特任助教 |
| 土屋 翔一 | 専修大学 | 講師 |
| 野口 健太 | 東京電機大学 | 助教 |
| 佐久間 雅 | 山形大学 | 准教授 |
|
【研究種目】基盤研究(B)
【研究期間】2012-04-01 - 2017-03-31
【配分額】9,880千円 (直接経費: 7,600千円、間接経費: 2,280千円)