禁止グラフ条件間の差の特徴付けと，その手法の確立

点击翻译按钮获取中文摘要

禁止グラフ条件によって生成されるグラフクラスの比較を行うために，前年度に引き続いて不変量版ラムゼー型問題の研究を進めた．本年度はそれに加えて，次数制約木の禁止グラフ条件に関する研究も実施した．ラムゼー型問題については，昨年度に行った誘導星道被覆数の研究が完結した．その結果として，同不変量に関するラムゼー型問題を解くことに成功している．この不変量は彩色数の連結版類似と見なすことができ，彩色数のラムゼー型問題はGyarfas-Sumner予想として有名な未解決問題である．したがって，本研究で与えた成果はGyarfas-Sumner予想に不変量的に近しい問題の解決を与えたと言える．次数制約木としては全域既約木に関連した問題に着手した．全域既約木を持つための禁止グラフ条件は2013年に完全決定されている．一方で証明手法が進展したことにより，全域既約木の構成の際に，次数２の頂点が（個数・独立性などの意味で）制約された全域木の存在性が重要であることが判明した．そこで本研究では，有用な次数２の頂点の制約を再整理し，それぞれの強弱関係と禁止グラフ条件の振る舞いの研究を開始した．実際には，全域木において次数２の頂点で誘導されるグラフの連結成分の大きさや，次数２の頂点の個数に関して４つの問題を提唱し，それぞれの禁止グラフ条件として必要な構造の列挙を行った．それらの十分性の証明はまだ完成していないものの，それらの有用な使用方法の確立には成功している．