2009/04/08 by Fouquet, Jean-Luc, Vanherpe, Jean-Marie
#Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.0904.1296
If G is a bridgeless cubic graph, Fulkerson conjectured that we can find 6 perfect matchings M1,...,M6 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 τ(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.