On Thomassen's conjecture and 2-factors of claw-free graphs

关于托马森猜想和无爪图的2-因子

• 批准号: 22540152
• 负责人: YOSHIMOTO Kiyoshi
• 金额: $ 2.75万
• 依托单位: Nihon University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2010
• 资助国家: 日本
• 起止时间: 2010-04-01 至 2014-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-22540152/
• 关键词: グラフ理論; ハミルトンサイクル; Thomassen予想; ２因子; ライングラフ; クローフリーグラフ; ３正則グラフ; 国際情報交換; claw-freeグラフ; Tutteサイクル; dominating偶部分グラフ; Jackson予想; Tutte閉トレイル; 2因子; 支配的サイクル; 線グラフ; Thomassenの予想; 最大独立数; 連結度; Ryjacek閉包

First, we studied the upper bounds of the number of components of 2-factors of low-connected line graphs, which are given by using the maximum independence number. And we got the following result: a 3-connected claw-free graph has a 2-factor in which the number of components is at most 2a/5, where a is the maximum independence number. Next we considered cubic graphs, which is very important family of graphs for Thomassen's conjecture and many important problems and conjectures in Graph theory. And we showed that if Bondy's conjecture on cubic graphs holds, then Thomassen's conjecture holds for the case of the minimum degree at least five.

首先，我们研究了低连通线图的2-因子分量数的上限，该上限是通过使用最大独立数给出的。我们得到以下结果：一个三连通无爪图有一个 2 因子，其中分量的数量最多为 2a/5，其中 a 是最大独立数。接下来我们考虑三次图，它是托马森猜想以及图论中许多重要问题和猜想的非常重要的图族。我们证明，如果邦迪关于三次图的猜想成立，那么托马森猜想对于最小度至少为五的情况也成立。

项目成果

2-factors and independent sets on claw-free graphs

无爪图上的 2 因子和独立集

• DOI: 10.1016/j.disc.2011.08.020
• 发表时间: 2012
• 期刊: Discrete Mathematics
• 影响因子: 0.8
• 作者: R.Kuzel;K.Ozeki;K.Yoshimoto
• 通讯作者: K.Yoshimoto

{4,5} is not coverable : a counterexample to a conjecture of Kaiser and Skrekovski

{4,5} 不可覆盖：Kaiser 和 Skrekovski 猜想的反例

• DOI: 10.1137/120877817
• 发表时间: 2013
• 期刊: SIAM J. Discrete Math
• 作者: R. Cada;S. Chiba;K. Ozeki;P. Vrana;K. Yoshimoto
• 通讯作者: K. Yoshimoto

A 2-factor in which each cycle has long length in claw-free graphs

无爪图中每个周期具有较长长度的 2 因子

• DOI: 10.1007/s00373-013-1375-z
• 发表时间: 2015
• 期刊: Graphs and Combin.
• 作者: R. Cada;S. Chiba and K. Yoshimoto
• 通讯作者: S. Chiba and K. Yoshimoto

Set-ordered as a generalization of k-ordered

集合有序作为 k 有序的推广

• DOI: 10.1016/j.disc.2010.05.005
• 发表时间: 2010
• 期刊: Discrete Math.
• 作者: K. Ishii;K. Ozeki and K. Yoshimoto
• 通讯作者: K. Ozeki and K. Yoshimoto

Locating Sets of Vertices on Hamiltonian Cycles

定位哈密顿环上的顶点集

• 发表时间: 2016
• 期刊: Discrete Applied Mathematics
• 影响因子: 1.1
• 作者: R. Faudree;H. Li and K. Yoshimoto
• 通讯作者: H. Li and K. Yoshimoto