A Sharp Dirac–Erdős Type Bound for Large Graphs

DOI10.1017/S0963548318000020zbMATH Open1390.05108arXiv1707.03892MaRDI QIDQ4635509FDOQ4635509

H. A. Kierstead, Andrew McConvey, Alexandr Kostochka

Publication date: 23 April 2018

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

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.

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)

Cites Work

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

Cited In (3)

• Sharp bounds on the order, size, and stability number of graphs
• A Bernstein inequality for exponentially growing graphs
• The asymptotics of large constrained 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)