TY - JOUR
T1 - Ore-type conditions implying 2-factors consisting of short cycles
AU - Kostochka, Alexandr V.
AU - Yu, Gexin
N1 - Funding Information:
We thank the referees for helpful remarks. The first author’s research was supported in part by the NSF grant DMS-0650784 and the RFBR grant 05-01-00816. The second author’s research was supported in part by the NSF grant DMS-0652306.
PY - 2009/7/28
Y1 - 2009/7/28
N2 - For every graph G, let σ2 (G) = min {d (x) + d (y) : x y ∉ E (G)}. The main result of the paper says that every n-vertex graph G with σ2 (G) ≥ frac(4 n, 3) - 1 contains each spanning subgraph H all whose components are isomorphic to graphs in {K1, K2, C3, K4-, C5+}. This generalizes the earlier results of Justesen, Enomoto, and Wang, and is a step towards an Ore-type analogue of the Bollobás-Eldridge-Catlin Conjecture.
AB - For every graph G, let σ2 (G) = min {d (x) + d (y) : x y ∉ E (G)}. The main result of the paper says that every n-vertex graph G with σ2 (G) ≥ frac(4 n, 3) - 1 contains each spanning subgraph H all whose components are isomorphic to graphs in {K1, K2, C3, K4-, C5+}. This generalizes the earlier results of Justesen, Enomoto, and Wang, and is a step towards an Ore-type analogue of the Bollobás-Eldridge-Catlin Conjecture.
KW - Degree conditions
KW - Packing
UR - http://www.scopus.com/inward/record.url?scp=67249095725&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=67249095725&partnerID=8YFLogxK
U2 - 10.1016/j.disc.2008.06.001
DO - 10.1016/j.disc.2008.06.001
M3 - Article
AN - SCOPUS:67249095725
SN - 0012-365X
VL - 309
SP - 4762
EP - 4771
JO - Discrete Mathematics
JF - Discrete Mathematics
IS - 14
ER -