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

DOI10.1017/S0963548318000020MaRDI QIDQ4635509zbMATH OpenFDO

Authors Andrew McConvey, H. A. Kierstead, Alexandr Kostochka

Publication date 23 April 2018

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1707.03892

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: Let $kgeq3$ be an integer, $h_k(G)$ be the number of vertices of degree at least $2k$ in a graph $G$, and $el{l}_k(G)$ be the number of vertices of degree at most $2k-2$ in $G$. Dirac and ErdH{o}s proved in 1963 that if $h_k(G)-el{l}_k(G)geq{k}^2+2k-4$, then $G$ contains $k$ vertex-disjoint cycles. For each $kgeq2$, they also showed an infinite sequence of graphs $G_k(n)$ with $h_k(G_k(n))-el{l}_k(G_k(n))=2k-1$ such that $G_k(n)$ does not have $k$ disjoint cycles. Recently, the authors proved that, for $kgeq2$, a bound of $3k$ is sufficient to guarantee the existence of $k$ disjoint cycles and presented for every $k$ a graph $G_0(k)$ with $h_k(G_0(k))-el{l}_k(G_0(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-ErdH{o}s construction is optimal in the sense that for every $kgeq2$, there are only finitely many graphs $G$ with $h_k(G)-el{l}_k(G)geq2k$ but no $k$ disjoint cycles. In particular, every graph $G$ with $|V(G)|geq19k$ and $h_k(G)-el{l}_k(G)geq2k$ contains $k$ disjoint cycles.

Recommendations

• Strengthening Theorems of Dirac and Erdős on Disjoint Cycles
• On the Corrádi-Hajnal theorem and a question of Dirac
• Disjoint long cycles in a graph
• Disjoint cycles in graphs with restricted independence number
• The \((2k-1)\)-connected multigraphs with at most \(k-1\) disjoint cycles

Cites work

• scientific article; zbMATH DE number 4085592 (Why is no real title available?)
• scientific article; zbMATH DE number 3344609 (Why is no real title available?)
• A refinement of a result of Corrádi and Hajnal
• An Ore-type theorem on equitable coloring
• Minimum degree conditions for vertex-disjoint even cycles in large graphs
• On the Corrádi-Hajnal theorem and a question of Dirac
• On the existence of disjoint cycles in a graph
• On the maximal number of independent circuits in a graph
• On the maximal number of independent circuits in a graph
• On the maximum number of independent cycles in a graph
• Sharpening an ore-type version of the Corrádi-Hajnal theorem
• Some Results Concerning the Structure of Graphs
• Strengthening Theorems of Dirac and Erdős on Disjoint Cycles

Cited in

(4)

• A Bernstein inequality for exponentially growing graphs
• The \((2k-1)\)-connected multigraphs with at most \(k-1\) disjoint cycles
• The asymptotics of large constrained graphs
• Sharp bounds on the order, size, and stability number of graphs

This page was built for publication: A sharp Dirac-Erdős type bound for large graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4635509)