極値グラフ理論の問題は, グラフHを固定するとき, 与えられたグラフGがHと同型な部分グラフを含むための辺数あるいは最小次数に関する最善の十分条件を求めることである。本研究では, 因子問題, マイナー, 部分グラフに関する問題を統一的な視点から俯瞰することにより, 新たな問題提起を行い, 展開研究を行った。とくに, 森グラフの極値問題, 弦付きサイクルやシータグラフを点素に見つける問題, マッチング拡張性などを重点的に扱った。また, グラフ理論の大きな未解決問題の一つであるHadwiger予想との関連において, グラフのρ彩色の概念を導入し, 次数列に関するHadwiger予想の簡潔な証明を与えた。
The problems in extremal graph theory is to find the minimum number of edges or a sharp minimum degree condition for a graph G to contain a prescribed subgraph H. In this research, by considering the problems from the unified point of view of factor problems, graph minor problems, and subgraph finding problems, we shall go into a new area of extremal graph theory. In particular, we focus on extremal problems of forests, vertex-disjoint chorded cycles and theta subgraphs, matching extendability, etc. Also, related to Hadwiger's conjecture, one of the most famous conjectures in graph theory, we propose the notion of rho-coloring, and give an alternative and much simpler proof of Hadwiger's conjecture for degree sequences.

研究種目 : 基盤研究(B)(一般)
研究期間 : 2012～2016
課題番号 : 24340021
研究分野 : 離散数学