Back to Search
Start Over
A refinement of theorems on vertex-disjoint chorded cycles
- 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.
- Subjects :
- Vertex (graph theory)
Conjecture
010102 general mathematics
0102 computer and information sciences
Disjoint sets
01 natural sciences
Graph
Theoretical Computer Science
Combinatorics
010201 computation theory & mathematics
05C35, 05C38, 05C75
FOS: Mathematics
Discrete Mathematics and Combinatorics
Mathematics - Combinatorics
Combinatorics (math.CO)
0101 mathematics
Mathematics
Subjects
Details
- Language :
- English
- Database :
- OpenAIRE
- Accession number :
- edsair.doi.dedup.....8ac09063e8af6edf15db74a15846f3cd