Conjecture (Berge and Fulkerson): Every 2-connected cubic graph has a collection of six perfect matchings that together cover every edge exactly twice.
This conjecture is attributed to Berge in [2]. The first printed appearance is in [1].
A good indication that this conjecture might be true is that the Petersen graph is not a counterexample. Note that every 3-edge-colorable cubic graph trivially satisfies the conjecture.
The problem can also be phrased as a fractional edge coloring. That is, each edge receives two ``half colors'' so that no half color is repeated at a vertex.
Mike Albertson asked if the conjecture is easier for toroidal graphs. He can show that there are 7 matchings together containing every edge exactly twice. He asked if there are 3 matchings that collectively cover all but two edges in a 2-connected toroidal cubic graph.
Archdeacon, Bonnington, and Siran (unpublished work) have examined many non-3-edge-colorable graphs of small order and have verified that they satisify the conjecture.
The following weaker version of the conjecture is also due to Berge (unpublished):
Conjecture (Berge): Every 2-connected cubic graph has a collection of five perfect matchings that together cover all edges of the graph.
The famous Cycle double cover conjecture can be viewed as a dual to the Berge-Fulkerson Conjecture.
References:
[1] D.R. Fulkerson, Blocking and anti-blocking pairs of polyhedra, Math. Programming 1 (1971) 168-194.
[2] P.D. Seymour, On multi-colourings of cubic graphs, and conjectures of Fulkerson and Tutte, Proc. London Math. Soc. (3) 38 (1979) 423-460.
Send comments to Bojan.Mohar@uni-lj.si