Pairwise Disjoint Perfect Matchings in r-Edge-Connected r-Regular Graphs

DOI10.1137/22M1500654MaRDI QIDQ6170446zbMATH OpenOpenAlexFDO

Authors Yulai Ma, Davide Mattiolo, Eckhard Steffen, Isaak H. Wolf

Publication date 10 August 2023

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2206.10975

zbMATH Keywords

\(r\)-graphsclass 2 graphsedge coloringsfactorsperfect matchingsregular graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Connectivity (05C40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: Thomassen [Problem 1 in Factorizing regular graphs, J. Combin. Theory Ser. B, 141 (2020), 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 $requiv2extmod4$. Together with a recent result of Mattiolo and Steffen [Highly edge-connected regular graphs without large factorizable subgraphs, J. Graph Theory, 99 (2022), 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.

Recommendations

• Highly edge‐connected regular graphs without large factorizable subgraphs
• scientific article; zbMATH DE number 1916568
• On the number of disjoint perfect matchings of regular graphs with given edge connectivity
• Unions of perfect matchings in \(r\)-graphs
• Disjoint odd circuits in a bridgeless cubic graph can be quelled by a single perfect matching

Cites work

• A Reduction Method for Edge-Connectivity in Graphs
• Blocking and anti-blocking pairs of polyhedra
• Chromatic-index-critical graphs of even order
• Cycles Intersecting Edge-Cuts of Prescribed Sizes
• Edge-colouring eight-regular planar graphs
• Factorizing regular graphs
• Factors and factorizations of graphs. Proof techniques in factor theory
• Fulkerson's conjecture and circuit covers
• Graph theory
• Highly edge‐connected regular graphs without large factorizable subgraphs
• Indecomposabler-graphs and some other counterexamples
• On Multi-Colourings of Cubic Graphs, and Conjectures of Fulkerson and Tutte
• On two consequences of Berge-Fulkerson conjecture
• Proof of the 1-factorization and Hamilton Decomposition Conjectures
• Reduction of the Berge-Fulkerson conjecture to cyclically 5-edge-connected snarks
• Regular n-valent n-connected non-Hamiltonian non n-edge-colourable graphs

Cited in

(9)

• Highly edge‐connected regular graphs without large factorizable subgraphs
• Edge-connectivity and pairwise disjoint perfect matchings in regular graphs
• The hardness of recognising poorly matchable graphs and the hunting of the \(d\)-snark
• On a conjecture that strengthens Kundu's k-factor theorem
• Sets of r-graphs that color all r-graphs
• Non-conflicting no-where zero Z₂ Z₂-flows in cubic graphs
• Cubic graphs with edges in exactly one perfect matching
• On the number of disjoint perfect matchings of regular graphs with given edge connectivity
• On edge-disjoint pairs of matchings

This page was built for publication: Pairwise Disjoint Perfect Matchings in r-Edge-Connected r-Regular Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6170446)