pith. sign in

arxiv: 1511.04356 · v1 · pith:YRLLFQ7Lnew · submitted 2015-11-13 · 🧮 math.CO

A refinement of theorems on vertex-disjoint chorded cycles

classification 🧮 math.CO
keywords cyclesleastminimumvertex-disjointchordedcontainsgraphdegree
0
0 comments X
read the original abstract

In 1963, Corr\'adi and Hajnal settled a conjecture of Erd\H{o}s by proving that, for all $k \geq 1$, any graph $G$ with $|G| \geq 3k$ and minimum degree at least $2k$ contains $k$ vertex-disjoint cycles. In 2008, Finkel proved that for all $k \geq 1$, any graph $G$ with $|G| \geq 4k$ and minimum degree at least $3k$ contains $k$ vertex-disjoint chorded cycles. Finkel's result was strengthened by Chiba, Fujita, Gao, and Li in 2010, who showed, among other results, that for all $k \geq 1$, any graph $G$ with $|G| \geq 4k$ and minimum Ore-degree at least $6k-1$ contains $k$ vertex-disjoint cycles. We refine this result, characterizing the graphs $G$ with $|G| \geq 4k$ and minimum Ore-degree at least $6k-2$ that do not have $k$ disjoint chorded cycles.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.