A sharp Dirac-Erdős type bound for large graphs

2017/07/12 by Kierstead, Henry A., Kostochka, Alexandr V., McConvey, Andrew
#05C10 #05C35 #05C70 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1707.03892

Abstract

Let k ≥ 3 be an integer, h_k(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 Erdős proved in 1963 that if h_k(G) - ℓ_k(G) ≥ k² + 2k - 4, then G contains k vertex-disjoint cycles. For each k≥ 2, they also showed an infinite sequence of graphs G_k(n) with h_k(G_k(n)) - ℓ_k(G_k(n)) = 2k-1 such that G_k(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 G₀(k) with h_k(G₀(k)) - ℓ_k(G₀(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-Erdős construction is optimal in the sense that for every k ≥ 2, there are only finitely many graphs G with h_k(G) - ℓ_k(G) ≥ 2k but no k disjoint cycles. In particular, every graph G with |V(G)| ≥ 19k and h_k(G) - ℓ_k(G) ≥ 2k contains k disjoint cycles.

Related

• Strengthening theorems of Dirac and Erdős on disjoint cycles
• On the Corrádi-Hajnal Theorem and a question of Dirac
• A refinement of theorems on vertex-disjoint chorded cycles
• The confirmation of a conjecture on disjoint cycles in a graph
• Longest Cycle above Erdős-Gallai Bound