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 -