Back to Search Start Over

PAIRWISE DISJOINT PERFECT MATCHINGS IN r-EDGE-CONNECTED r-REGULAR GRAPHS.

Authors :
YULAI MA
MATTIOLO, DAVIDE
STEFFEN, ECKHARD
WOLF, ISAAK H.
Source :
SIAM Journal on Discrete Mathematics. 2023, Vol. 37 Issue 3, p1548-1585. 18p.
Publication Year :
2023

Abstract

Thomassen [J. Combin. Theory Ser. B, 141 (2020), pp. 343--351] asked whether every r-edge-connected r-regular graph of even order has r 2 pairwise disjoint perfect matchings. We show that this is not the case if r = 2 mod 4. Together with a recent result of Mattiolo and Steffen [J. Graph Theory, 99 (2022), pp. 107--116] this solves Thomassen's problem for all even r. It turns out that our methods are limited to the even case of Thomassen's problem. We then prove some equivalences of statements on pairwise disjoint perfect matchings in highly edge-connected regular graphs, where the perfect matchings contain or avoid fixed sets of edges. Based on these results we relate statements on pairwise disjoint perfect matchings of 5-edge-connected 5-regular graphs to well-known conjectures for cubic graphs, such as the Fan--Raspaud conjecture, the Berge--Fulkerson conjecture, and the 5-cycle double cover conjecture. [ABSTRACT FROM AUTHOR]

Details

Language :
English
ISSN :
08954801
Volume :
37
Issue :
3
Database :
Academic Search Index
Journal :
SIAM Journal on Discrete Mathematics
Publication Type :
Academic Journal
Accession number :
173328531
Full Text :
https://doi.org/10.1137/22M1500654