極値グラフ理論的観点による完全多部グラフマイナーのスペクトラム解析

极值图论视角下的完全多方图挖掘机谱分析

• 批准号: 22K13956
• 负责人: 前澤 俊一
• 金额: $ 2.91万
• 依托单位: Tokyo University of Science
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Early-Career Scientists
• 财政年份: 2022
• 资助国家: 日本
• 起止时间: 2022-04-01 至 2025-03-31
• 项目状态: 未结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-22K13956/
• 关键词: グラフマイナー; 次数条件; 平面的グラフ; 密グラフ; 極値グラフ理論

本研究の目的は極値グラフ理論的観点から完全多部グラフマイナーのスペクトラム解析である．目的達成のため，本研究では辺の本数が頂点数に比べて多いグラフ（密なグラフ）の構造解析，そして，平面的グラフに関する研究を行った．以下，本研究に関係する結果の詳細を記載する．1つ目の結果は平面的グラフが(m,n)-linkedであるための必要十分条件を与えたものである．既存の結果では平面的グラフが(3,3)-linkedであるための必要十分条件を与えていたが，本研究ではその一般化に成功している．頂点数の少ないグラフのマイナーを見つける際には，対象となるグラフに平面的グラフに近い性質が出てくることがある．そのため，本研究は頂点数の少ないグラフのマイナーを見つける研究と関連している．本研究成果は国際誌Graphs and Combinatoricsに受理されている．2つ目の結果は辺連結度の高いグラフには任意の向き付けから，辺のフリップ操作によって辺連結度を下げることなく，高い辺連結度の有向グラフにすることができることを示している．これはグラフ間の構造解析を行ったものであり，本研究課題のスペクトラム解析にも関連する．本研究成果は査読付き国際会議Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithmsと国際誌ACM Transactions on Algorithmsにすでに受理されている．また，このほかにも査読付き国際誌に1本の論文が受理されており，査読付き国際会議に4つの結果が受理されている．さらに，現在，査読付き国際誌に3編の論文を投稿中である．

The purpose of this study is to analyze the complete multi-part transformation from the extreme value theory to the extreme value theory. The purpose of this study is to study the structural analysis of the number of vertices and the relationship between the number of vertices and the number of vertices. The results of this study are described in detail below. 1. The results of this study are planar (m,n)-linked and the necessary ten conditions are related to each other. The existing results are the necessary conditions for the plane's (3,3)-linked The number of vertices is less than the number of vertices. The number of vertices is less than the number of vertices. This paper studies the relationship between the number of vertices and the number of vertices. The results of this study are accepted in the international journal Graphs and Combinatorics. 2. The results of this study are as follows: 1. The high degree of connectivity and the high degree of connectivity are the results of the arbitrary direction of connectivity. 2. The high degree of connectivity and the high degree of connectivity are the results of the arbitrary direction of connectivity. The structure analysis of this research topic is related to the structure analysis. The results of this study were reviewed in the Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms and ACM Transactions on Algorithms. This paper is accepted for the first time, and the results of the international conference are accepted for the second time. Today, now, check out the International Journal of Fu Qi 3 series of papers submitted in the middle of the article.

项目成果

辺着色グラフがproperly colored spanning treeを持つための色次数条件

边缘彩色图具有正确着色的生成树的颜色顺序条件

• 发表时间: 2023
• 作者: Maezawa Shun-ichi;Yazawa Akiko;森竜樹;前澤 俊一
• 通讯作者: 前澤 俊一

木における誘導マッチング遷移

树中的引导匹配过渡

• 发表时间: 2022
• 作者: 森竜樹;田崎創平;辻川亨;四ツ谷晶二;前澤 俊一;前澤 俊一
• 通讯作者: 前澤 俊一

外平面的グラフのDP-degree-coloring

外部平面图的 DP 度着色

• 发表时间: 2022
• 作者: 森竜樹;田崎創平;辻川亨;四ツ谷晶二;前澤 俊一;前澤 俊一;前澤 俊一
• 通讯作者: 前澤 俊一

Monotone edge flips to an orientation of maximum edge-connectivity a la Nash-Williams

单调边缘翻转到最大边缘连通性的方向，如纳什-威廉姆斯

• DOI: 10.1145/3561302
• 发表时间: 2023
• 期刊: ACM Transactions on Algorithms
• 影响因子: 1.3
• 作者: Takehiro Ito;Yuni Iwamasa;Naonori Kakimura;Naoyuki Kamiyama;Yusuke Kobayashi;Shun-ichi Maezawa;Yuta Nozaki;Yoshio Okamoto;Kenta Ozeki
• 通讯作者: Kenta Ozeki

Special Case of Rota's Basis Conjecture on Graphic Matroids

图拟阵上罗塔基本猜想的特例

• DOI: 10.37236/10835
• 发表时间: 2022
• 期刊: The Electronic Journal of Combinatorics
• 作者: Maezawa Shun-ichi;Yazawa Akiko
• 通讯作者: Yazawa Akiko