权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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

探索图结构理论与着色理论交叉的前沿

基本信息

批准号：
22K20343
负责人：
林興養
金额：
$ 1.5万
依托单位：
Chuo University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Research Activity Start-up
财政年份：
2022
资助国家：
日本
起止时间：
2022-08-31 至 2024-03-31
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-22K20343/
关键词：
グラフ彩色マイナー細分アルゴリズム組合せ最適化

项目摘要

構造的グラフ理論において, 四色問題を拡張した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の彩色予想の位数最小反例の連結度を上げる議論がより単純な部分問題に帰着された. 本結果をまとめた論文を査読付き論文誌に投稿した.

In the theory of construction, the four-color problem is expanded by Hadwiger and Hajos, and the coloring number of the large domain is directly affected by the partial structure of the structure. In particular, Hajos expects that 5 vertices are completely divided into 4 colors, which are difficult to ask, and specific subdivisions are prohibited. A set of important problems, specifying the existence of 4 vertex bifurcation points and subdivision problems,"4 vertex root subdivision problems," construction theorems for root subdivision problems, and the results of 6 links in force, Japanese Conference on Combinatorics and its Applications(Discrete Mathematics and Applications Research Conference)2022. McCarty et al. (2020). The construction theorem of 4-link finite element analysis is obtained. It is proved that the root of the theorem is to make use of the tripod and the structure of the structure to make use of the structure. The results show that Hajos's color prediction has the lowest number of counterexamples and the link degree is higher than that of the pure part of the problem. The results of this paper were reviewed and published.