TY - JOUR

T1 - A Sharp Dirac-Erdos Type Bound for Large Graphs

AU - Kierstead, H. A.

AU - Kostochka, A. V.

AU - Mcconvey, A.

N1 - Funding Information:
† Research of this author is supported in part by NSF grant DMS-1600592 and by grants 15-01-05867 and 16-01-00499 of the Russian Foundation for Basic Research. ‡ This author gratefully acknowledges support from the Campus Research Board, University of Illinois.
Publisher Copyright:
© Copyright Cambridge University Press 2018.

PY - 2018/5/1

Y1 - 2018/5/1

N2 - Let k ≥ 3 be an integer, hk(G) be the number of vertices of degree at least 2k in a graph G, and ℓk(G) be the number of vertices of degree at most 2k - 2 in G. Dirac and Erdos proved in 1963 that if hk(G) - ℓk(G) ≥ k2 + 2k - 4, then G contains k vertex-disjoint cycles. For each k ≥ 2, they also showed an infinite sequence of graphs Gk(n) with hk(Gk(n)) - ℓk(Gk(n)) = 2k - 1 such that Gk(n) does not have k disjoint cycles. Recently, the authors proved that, for k ≥ 2, a bound of 3k is sufficient to guarantee the existence of k disjoint cycles, and presented for every k a graph G0(k) with hk(G0(k)) - ℓk(G0(k)) = 3k - 1 and no k disjoint cycles. The goal of this paper is to refine and sharpen this result. We show that the Dirac-Erdos construction is optimal in the sense that for every k ≥ 2, there are only finitely many graphs G with hk(G) - ℓk(G) ≥ 2k but no k disjoint cycles. In particular, every graph G with |V(G)| ≥ 19k and hk(G) - ℓk(G) ≥ 2k contains k disjoint cycles.

AB - Let k ≥ 3 be an integer, hk(G) be the number of vertices of degree at least 2k in a graph G, and ℓk(G) be the number of vertices of degree at most 2k - 2 in G. Dirac and Erdos proved in 1963 that if hk(G) - ℓk(G) ≥ k2 + 2k - 4, then G contains k vertex-disjoint cycles. For each k ≥ 2, they also showed an infinite sequence of graphs Gk(n) with hk(Gk(n)) - ℓk(Gk(n)) = 2k - 1 such that Gk(n) does not have k disjoint cycles. Recently, the authors proved that, for k ≥ 2, a bound of 3k is sufficient to guarantee the existence of k disjoint cycles, and presented for every k a graph G0(k) with hk(G0(k)) - ℓk(G0(k)) = 3k - 1 and no k disjoint cycles. The goal of this paper is to refine and sharpen this result. We show that the Dirac-Erdos construction is optimal in the sense that for every k ≥ 2, there are only finitely many graphs G with hk(G) - ℓk(G) ≥ 2k but no k disjoint cycles. In particular, every graph G with |V(G)| ≥ 19k and hk(G) - ℓk(G) ≥ 2k contains k disjoint cycles.

UR - http://www.scopus.com/inward/record.url?scp=85043307486&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85043307486&partnerID=8YFLogxK

U2 - 10.1017/S0963548318000020

DO - 10.1017/S0963548318000020

M3 - Article

AN - SCOPUS:85043307486

SN - 0963-5483

VL - 27

SP - 387

EP - 397

JO - Combinatorics Probability and Computing

JF - Combinatorics Probability and Computing

IS - 3

ER -