Disjoint cycles and chorded cycles in a graph with given minimum degree
Disjoint cycles and chorded cycles in a graph with given minimum degree
复制标题
图中具有给定最小度数的不相交循环和弦循环
DOI：
10.1016/j.disc.2020.111837
复制
发表时间：
2020
影响因子：
0.8
通讯作者：
Yeager, Elyse
中科院分区：
文献类型：
--
作者：
Molla, Theodore;Santana, Michael;Yeager, Elyse
1963年Corrádi和Hajnal解决了Erdős的一个猜想，证明了在至少3r个顶点上最小度至少为2r的图包含r个不相交环的集合，2008年Finkel证明了在至少4s个顶点上最小度至少为3s的图包含s个不相交环的集合。同年，Bialostocki、Finkel和Gyárfás对这一定理进行了推广：每个至少有3r + 4s个顶点，最小度至少为2r + 3s的图都包含r+ s个不相交环的集合，其中s个是有弦的。Chiba et al.（2010）证实并进一步强化了这一猜想。在本文中，我们刻画了在至少3r + 4s个顶点上的所有图，这些顶点的最小度至少为2r + 3s−1，它们不包含r+ s个不相交环的集合，其中s个环是有弦的。此外，我们给出了r+ s不相交环存在的最小度阈值的一个猜想，其中s个环有弦，我们证明了这个猜想的一个近似版本。
In 1963, Corrádi and Hajnal settled a conjecture of Erdős by showing that every graph on at least 3 r vertices with minimum degree at least 2 r contains a collection of r disjoint cycles, and in 2008, Finkel proved that every graph with at least 4 s vertices and minimum degree at least 3 s contains a collection of s disjoint chorded cycles. The same year, a generalization of this theorem was conjectured by Bialostocki, Finkel, and Gyárfás: every graph with at least 3 r+ 4 s vertices and minimum degree at least 2 r+ 3 s contains a collection of r+ s disjoint cycles, s of them chorded. This conjecture was settled and further strengthened by Chiba et al.(2010). In this paper, we characterize all graphs on at least 3 r+ 4 s vertices with minimum degree at least 2 r+ 3 s− 1 that do not contain a collection of r+ s disjoint cycles, s of them chorded. In addition, we provide a conjecture regarding the minimum degree threshold for the existence of r+ s disjoint cycles, s of them chorded, and we prove an approximate version of this conjecture.
登录
查看更多内容
DOI：
10.1016/j.jctb.2016.05.007
发表时间：
2016-01
期刊：
J. Comb. Theory B
影响因子：
--
作者：
H. Kierstead;A. Kostochka;E. Yeager
通讯作者：
H. Kierstead;A. Kostochka;E. Yeager
影响因子：
0.7
作者：
S. Chiba;S. Fujita;Yunshu Gao;Guojun Li
通讯作者：
S. Chiba;S. Fujita;Yunshu Gao;Guojun Li
K4−图表中的因子
影响因子：
0.9
作者：
K. Kawarabayashi
通讯作者：
K. Kawarabayashi
Komlós 平铺猜想的证明
影响因子：
1
作者：
A. Shokoufandeh;Yi Zhao
通讯作者：
Yi Zhao