Covering a cubic graph by 5 perfect matchings

DOI10.1016/J.DISC.2017.03.014MaRDI QIDQ2397531zbMATHOpenAlexFDO

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

cubic graphhypo-Hamiltonian graphBerge conjectureFulkerson conjectureperfect 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

• scientific article; zbMATH DE number 227006 (Why is no real title available?)
• 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
• On Fulkerson conjecture
• On Multi-Colourings of Cubic Graphs, and Conjectures of Fulkerson and Tutte
• On perfect matching coverings and even subgraph coverings
• The Factorization of Linear Graphs
• The equivalence of two conjectures of Berge and Fulkerson
• Treelike snarks

Cited in

(7)

• Dihedral covers of the complete graph \(K_5\)
• Perfect matching covers of cubic graphs of oddness 2
• Cubic graphs that cannot be covered with four perfect matchings
• Covering a cubic graph with perfect matchings
• Unions of perfect matchings in \(r\)-graphs
• On perfect matching coverings and even subgraph coverings
• A class of cubic graphs satisfying Berge conjecture

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)