Strengthening Theorems of Dirac and Erdős on Disjoint Cycles

DOI10.1002/JGT.22106MaRDI QIDQ4978446zbMATH OpenOpenAlexFDO

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

Publication date 10 August 2017

Published in Journal of Graph Theory (Search for Journal in Brave)

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

zbMATH Keywords

disjoint cyclesdisjoint trianglesminimum degreeplanar graphs

Mathematics Subject Classification ID

Vertex degrees (05C07) Planar graphs; geometric and topological aspects of graph theory (05C10) Extremal problems in graph theory (05C35) Paths and cycles (05C38)

Abstract: Let $kge3$ be an integer, $H_k(G)$ be the set of vertices of degree at least $2k$ in a graph $G$, and $L_k(G)$ be the set of vertices of degree at most $2k-2$ in $G$. In 1963, Dirac and ErdH{o}s proved that $G$ contains $k$ (vertex-)disjoint cycles whenever $|H_k(G)|-|L_k(G)|ge{k}^2+2k-4$. The main result of this paper is that for $kge2$, every graph $G$ with $|V(G)|ge3k$ containing at most $t$ disjoint triangles and with $|H_k(G)|-|L_k(G)|ge2k+t$ contains $k$ disjoint cycles. This yields that if $kge2$ and $|H_k(G)|-|L_k(G)|ge3k$, then $G$ contains $k$ disjoint cycles. This generalizes the Corr'{a}di-Hajnal Theorem, which states that every graph $G$ with $H_k(G)=V(G)$ and $|H_k(G)|ge3k$ contains $k$ disjoint cycles.

Recommendations

• A strengthening of the Erdős-Szekeres theorem
• An improved bound for disjoint directed cycles
• A unified Erdős-Pósa theorem for constrained cycles
• On a conjecture of Erdős and Simonovits: even cycles
• A conjecture of Verstraëte on vertex-disjoint cycles
• scientific article; zbMATH DE number 4213130
• Stability in the Erdős-Gallai theorems on cycles and paths
• On stronger conjectures that imply the Erdős-Moser conjecture
• A refinement of theorems on vertex-disjoint chorded cycles
• A strengthening of Erdős-Gallai theorem and proof of Woodall's conjecture

Cites work

• A refinement of a result of Corrádi and Hajnal
• An extension of the Hajnal-Szemerédi theorem to directed graphs
• An Ore-type theorem on equitable coloring
• Independent directed triangles in a directed graph
• Minimum degree conditions for vertex-disjoint even cycles in large graphs
• On directed versions of the Corrádi-Hajnal corollary
• On directed versions of the Hajnal-Szemerédi theorem
• 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

Cited in

(8)

• Sharpening an ore-type version of the Corrádi-Hajnal theorem
• The \((2k-1)\)-connected multigraphs with at most \(k-1\) disjoint cycles
• Degree conditions for the existence of vertex-disjoint cycles and paths: a survey
• An algorithmic answer to the Ore-type version of Dirac's question on disjoint cycles
• A unified Erdős-Pósa theorem for constrained cycles
• A sharp Dirac-Erdős type bound for large graphs
• A new result on disjoint cycles in graphs
• A simpler proof for the two disjoint odd cycles theorem

This page was built for publication: Strengthening Theorems of Dirac and Erdős on Disjoint Cycles

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