TY - CHAP
T1 - Disjoint Chorded Cycles in Graphs with High Ore-Degree
AU - Kostochka, Alexandr
AU - Yager, Derrek
AU - Yu, Gexin
N1 - Publisher Copyright:
© 2020, Springer Nature Switzerland AG.
PY - 2020
Y1 - 2020
N2 - In 1963, Corrádi and Hajnal proved that for all k ≥ 1, every graph with at least 3k vertices and minimum degree at least 2k has k vertex-disjoint chorded cycles. In 2010, Chiba, Fujita, Gao, and Li proved that for all k ≥ 1, every graph with |G|≥ 4k and minimum Ore-degree at least 6k − 1 contains k (vertex-)disjoint chorded cycles. In 2016, Molla, Santana, and Yeager refined this to characterize all graphs with at least 4k vertices and minimum Ore-degree at least 6k − 2 that do not have k disjoint chorded cycles. We further strengthen this to characterize the graphs with Ore-degree at least 6k − 3 that do not have k disjoint chorded cycles.
AB - In 1963, Corrádi and Hajnal proved that for all k ≥ 1, every graph with at least 3k vertices and minimum degree at least 2k has k vertex-disjoint chorded cycles. In 2010, Chiba, Fujita, Gao, and Li proved that for all k ≥ 1, every graph with |G|≥ 4k and minimum Ore-degree at least 6k − 1 contains k (vertex-)disjoint chorded cycles. In 2016, Molla, Santana, and Yeager refined this to characterize all graphs with at least 4k vertices and minimum Ore-degree at least 6k − 2 that do not have k disjoint chorded cycles. We further strengthen this to characterize the graphs with Ore-degree at least 6k − 3 that do not have k disjoint chorded cycles.
KW - Chorded cycles
KW - Cycles
KW - Ore-degree
UR - http://www.scopus.com/inward/record.url?scp=85096608745&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85096608745&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-55857-4_11
DO - 10.1007/978-3-030-55857-4_11
M3 - Chapter
AN - SCOPUS:85096608745
T3 - Springer Optimization and Its Applications
SP - 259
EP - 304
BT - Springer Optimization and Its Applications
PB - Springer
ER -