Covering a cubic graph by 5 perfect matchings

DOI10.1016/J.DISC.2017.03.014MaRDI QIDQ2397531zbMATH OpenOpenAlexFDO

Authors Wuyang Sun

Publication date 22 May 2017

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

Berge conjecturecubic graphFulkerson conjecturehypo-Hamiltonian graphperfect matching cover

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: Berge Conjecture states that every bridgeless cubic graph has 5 perfect matchings such that each edge is contained in at least one of them. In this paper, we show that Berge Conjecture holds for two classes of cubic graphs, cubic graphs with a circuit missing only one vertex and bridgeless cubic graphs with a 2-factor consisting of two circuits. The first part of this result implies that Berge Conjecture holds for hypohamiltonian cubic graphs.

Recommendations

• A class of cubic graphs satisfying Berge conjecture
• Covering a cubic graph with perfect matchings
• Perfect matching covers of cubic graphs of oddness 2
• On perfect matching coverings and even subgraph coverings
• scientific article; zbMATH DE number 5130820

Cites work

• 1-factor and cycle covers of cubic graphs
• A note on Berge-Fulkerson coloring
• Blocking and anti-blocking pairs of polyhedra
• Fulkerson's conjecture and Loupekine snarks
• Fulkerson-covers of hypohamiltonian graphs
• scientific article; zbMATH DE number 227006 (Why is no real title available?)
• On Fulkerson conjecture
• On Multi-Colourings of Cubic Graphs, and Conjectures of Fulkerson and Tutte
• On perfect matching coverings and even subgraph coverings
• The equivalence of two conjectures of Berge and Fulkerson
• The Factorization of Linear Graphs
• Treelike snarks

Cited in

(10)

• Perfect matching covers of cubic graphs of oddness 2
• Cubic graphs that cannot be covered with four perfect matchings
• A class of cubic graphs satisfying Berge conjecture
• Dihedral covers of the complete graph K₅
• On perfect matching coverings and even subgraph coverings
• Covering a cubic graph with perfect matchings
• Unions of perfect matchings in \(r\)-graphs
• Perfect matching cover indices of generalized rotation snarks
• 4-coverable snarks, perfect matching cover, and Isaacs product
• An infinite family of snarks with perfect matching cover index 4

This page was built for publication: Covering a cubic graph by 5 perfect matchings

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