On the perfect matching index of bridgeless cubic graphs

Abstract

If $G$ is a bridgeless cubic graph, Fulkerson conjectured that we can find 6 perfect matchings $M_1,...,M_6$ of $G$ with the property that every edge of $G$ is contained in exactly two of them and Berge conjectured that its edge set can be covered by 5 perfect matchings. We define $\tau (G)$ as the least number of perfect matchings allowing to cover the edge set of a bridgeless cubic graph and we study this parameter. The set of graphs with perfect matching index 4 seems interesting and we give some informations on this class.

Cited by in corpus (11)

• 1-factor and cycle covers of cubic graphs
• Odd 2-factored snarks
• Covering a cubic graph with perfect matchings
• Some snarks are worse than others
• On measures of edge-uncolorability of cubic graphs: A brief survey and some new results
• Ban--Linial's Conjecture and treelike snarks
• Covering cubic graphs with matchings of large size
• Shortest cycle covers and cycle double covers with large 2-regular subgraphs
• On the excessive [m]-index of a tree
• Covering a cubic graph by 5 perfect matchings
• Betwixt and between 2-factor Hamiltonian and Perfect-Matching-Hamiltonian graphs