Forbidden subgraphs generating a finite set

禁止子图生成有限集

• 批准号: 22500018
• 负责人: SAITO Akira
• 金额: $ 2.66万
• 依托单位: Nihon University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2010
• 资助国家: 日本
• 起止时间: 2010 至 2012
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-22500018/
• 关键词: グラフ理論; 禁止部分グラフ; 誘導部分グラフ; 有限集合; 連結度; グラフ; 完全グラフ; スター; ２部グラフ; 道; 連結グラフ; 2-連結グラフ; パス

For a set of connected graphs F, a graph G is said to be F-free if G does not contain any member of F as an induced subgraph.The set F is often referred as forbidden subgraphs. In the research, we have studied the property of the forbidden subgraphs F such that the set of k-connected F-free graphs is a finite set. We have given acomplete characterization of F in the cases of |F|≦2 and k≦6 and of |F|=3 and k≦2.We have also obtained a partial characterization in the case of |F|=3 and k=3.

对于一个连通图集合F，称一个图G是F-free的，如果G不包含F的任何成员作为导出子图，集合F通常被称为禁止子图。在研究中，我们研究了禁止子图F的性质，使得k-连通无F-图的集合是有限集合。我们给出了F在以下情形下的完全特征|F| 2002年和2006年，|F|当k =3且k = 2时，我们还得到了一个局部特征|F| =3，k=3。

项目成果

List-coloring of graphs and cycles of length divisible by a given number

图表的列表着色和长度可被给定数字整除的循环

• 发表时间: 2010
• 期刊: Contemporary Mathematics
• 作者: S.Akbari;A.Doni;M.Ghanbari;S.Jahanbekam and A.Saito
• 通讯作者: S.Jahanbekam and A.Saito

The local Chvatal-Erdos condition and 2-factors

当地 Chvatal-Erdos 条件和 2 因素

• 发表时间: 2012
• 作者: R.E.L.Aldred;J.Fujisawa and A.Saito;R.E.L.Aldred;K.Kimura;S.Akbari;斎 藤明;斎 藤 明;Akira Saito;Akira Saito
• 通讯作者: Akira Saito

Forbidden subgraphs and 2-factors in graphs

图中的禁止子图和 2 因子

• 发表时间: 2012
• 作者: R.E.L.Aldred;J.Fujisawa and A.Saito;R.E.L.Aldred;K.Kimura;S.Akbari;斎 藤明;斎 藤 明;Akira Saito;Akira Saito;斎 藤 明;斎藤 明;斎藤明
• 通讯作者: 斎藤明

Closures, cycles, and paths

闭包、循环和路径

• DOI: 10.1002/jgt.20584
• 发表时间: 2012
• 期刊: Journal of Graph Theory
• 影响因子: 0.9
• 作者: J. Harant;A. Kemnitz;Akira Saito;I. Schiermeyer
• 通讯作者: I. Schiermeyer

Hamiltonian cycles with all small even chords

• DOI: 10.1016/j.disc.2011.12.013
• 发表时间: 2012-03
• 期刊: Discret. Math.
• 作者: Guantao Chen;K. Ota;Akira Saito;Yi Zhao