Back to Search Start Over

A refinement of theorems on vertex-disjoint chorded cycles

Authors :
Michael Santana
Theodore Molla
Elyse Yeager
Publication Year :
2015

Abstract

In 1963, Corradi and Hajnal settled a conjecture of Erd?s by proving that, for all $$k \ge 1$$k?1, any graph G with $$|G| \ge 3k$$|G|?3k and minimum degree at least 2k contains k vertex-disjoint cycles. In 2008, Finkel proved that for all $$k \ge 1$$k?1, any graph G with $$|G| \ge 4k$$|G|?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 \ge 1$$k?1, any graph G with $$|G| \ge 4k$$|G|?4k and minimum Ore-degree at least $$6k-1$$6k-1 contains k vertex-disjoint chorded cycles. We refine this result, characterizing the graphs G with $$|G| \ge 4k$$|G|?4k and minimum Ore-degree at least $$6k-2$$6k-2 that do not have k vertex-disjoint chorded cycles.

Details

Language :
English
Database :
OpenAIRE
Accession number :
edsair.doi.dedup.....8ac09063e8af6edf15db74a15846f3cd