TY - CHAP
T1 - Disjoint Chorded Cycles in Graphs with High Ore-Degree
AU - Kostochka, Alexandr
AU - Yager, Derrek
AU - Yu, Gexin
N1 - Acknowledgments This research of the author “Alexandr Kostochka” was supported in part by NSF grant DMS-1600592 and grants 18-01-00353A and 19-01-00682 of the Russian Foundation for Basic Research. This research of the author “Derrek Yager” was supported in part by Award RB17164 of the Research Board of the University of Illinois at Urbana-Champaign.
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 -