Research on graphs characterized by forbidden minors

禁止未成年人特征图谱研究

• 批准号: 20340023
• 负责人: OTA Katsuhiro
• 金额: $ 3.99万
• 依托单位: Keio University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (B)
• 财政年份: 2008
• 资助国家: 日本
• 起止时间: 2008 至 2011
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-20340023/
• 关键词: 組合せ論; グラフ; マイナー; 禁止マイナー; 禁止部分グラフ; 完全マッチング; クローフリーグラフ; タフネス; グラフ理論; グラフマイナー; 閉曲面上への埋め込み; 全域木

From a given graph G, a graph obtained from a subgraph of G by contracting several edges is called a minor of G. Some important classes of graphs, such as planar graphs are closed under the operation taking a minor, and are characterized by forbidden minors. In this research, we extend some results of planar graphs concerning cycles, spanning trees and factors, from the point of view of forbidden minors. In particular, we obtained some results on the toughness and the spanning trees in graphs without complete bipartite minors. We also considered similar problems on the forbidden induced subgraphs.

从一个给定的图G出发，由G的一个子图通过收缩几条边而得到的图称为G的一个子图。一些重要的图类，如平面图，在取子式运算下是闭的，并被禁止子式所刻画。本文从禁子式的观点出发，推广了平面图中关于圈、支撑树和因子的一些结果。特别地，我们得到了一些关于不含完全二部子图的坚韧度和生成树的结果。我们也考虑了禁止诱导子图的类似问题。

项目成果

3-連結グラフにおけるハミルトン性のための禁止部分グラフのペアについて

3 - 关于连通图中哈密顿性的禁止子图对

• 发表时间: 2012
• 作者: R. E. L. Aldred;J. Fujisawa;A. Saito;Masakazu Muramatsu and Hayato Waki;T.Kumagai;藤沢潤
• 通讯作者: 藤沢潤

Forbidden subgraphs for hamiltonicity of 3-connected graphs

3 连通图的半调性禁止子图

• 发表时间: 2011
• 作者: Kigami;Jun;Atsuhiro Nakamoto;Jun Kigami;相川弘明;藤沢潤
• 通讯作者: 藤沢潤

Forbidden subgraphs implying graph properties

暗示图属性的禁止子图

• 发表时间: 2010
• 作者: G. Sueiro;太田克弘;小関健太;藤沢潤
• 通讯作者: 藤沢潤

On $2$-Factors in $r$-Connected $\{K_{1,k},P_4\}$-Free Graphs

• DOI: 10.3836/tjm/1233844061
• 发表时间: 2008
• 期刊: Tokyo Journal of Mathematics
• 影响因子: 0.6
• 作者: Y. Egawa;J. Fujisawa;S. Fujita;K. Ota

Forbidden induced subgraphs for star-free graphs

• DOI: 10.1016/j.disc.2011.07.022
• 发表时间: 2011-11
• 期刊: Discret. Math.
• 作者: J. Fujisawa;K. Ota;K. Ozeki;Gabriel Sueiro