グラフの構造的理論と彩色理論が交差するフロンティアの開拓

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

構造的グラフ理論において, 四色問題を拡張したHadwiger予想やHajos予想は, グラフの大域的パラメータである染色数がグラフの部分構造へ与える直接的な影響を問う重要な未解決問題である. 特に, Hajos予想は, 5頂点完全グラフの細分を含まないグラフが4彩色可能であることを主張する難問であり, 特定の細分を禁止部分グラフとしてもつグラフ構造の理解が鍵となる. その重要な部分問題の一つが, 指定した4頂点を分岐点とする細分の存在を問う「4頂点上の根付き細分問題」である.4頂点単純グラフの根付き細分に対する構造定理として, 入力のグラフが6連結であることを仮定した場合の成果を, Japanese Conference on Combinatorics and its Applications(離散数学とその応用研究集会)2022にて発表した. この成果は, この分野における最先端の研究であるMcCarty et al. (2020)の拡張となっている.また, 4連結を仮定したグラフにおいて, 5頂点完全グラフの部分グラフに同相な根付き細分の存在を保証する構造定理を得た. その証明は, 根付きグラフマイナーや2パス定理で利用されるtripodと呼ばれる構造を利用した構成的なものである. 本結果により, Hajosの彩色予想の位数最小反例の連結度を上げる議論がより単純な部分問題に帰着された. 本結果をまとめた論文を査読付き論文誌に投稿した.