Double Covering Edges by Perfect Matchings
A perfect matching or 1-factor in a graph is a collection of edges which together are incident with every vertex exactly once. A 1-factorization is a partition of the edges into 1-factors. If the graph is regular of degree d, then a 1-factorization is equivalent to a proper edge d-coloring. A cubic graph is one that is regular of degree three.
Not every cubic graph can be edge-partitioned into perfect matchings. The Petersen graph is a counterexample. The following was conjectured (I believe independently) by Berge and by Fulkerson. I've heard it called the Berge-Fulkerson conjecture, but more frequently just Fulkerson's Conjecture (who I believe was the first to publish it).
Conjecture: Every bridgeless cubic graph has a collection of six perfect matchings together contain every edge exactly twice.
The Petersen graph is not a counterexample (so the conjecture must be true!); the six 1-factors form such a double cover. Note that any 3-edge-colorable cubic graph (Class 1) 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. An extension of this would allow 1-factors of arbitrary rational weight. Another variation would be to allow adding or subtracting 1-factors. I believe that these variations may be known.
Mike Albertson asks if the conjecture is easier for toroidal graphs. He can show that there are 7 matchings together containing every edge exactly twice. He asks if there are 3 matchings that collectively cover all but two edges in a bridgeless 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. In my opinion this is one of the most important open problems in the field.
A dual problem is called the Cycle double
cover conjecture. For relaxations see Covering
cubic graphs with perfect matchings and Perfect
matchings in cubic graphs that have empty intersection
[F] D.R. Fulkerson, Blocking and anti-blocking pairs of polyhedra, Math. Programming 1 (1971) 168-194.
[Se] P.D. Seymour, On multi-colourings of cubic graphs, and conjectures of Fulkerson and Tutte, Proc. London Math. Soc. (3) 38 (1979) 423-460.
Submitted by: Dan Archdeacon, Department of Mathematics and Statistics, University of Vermont, Burlington VT 05405 USA.
Send comments to firstname.lastname@example.org
August 1995, modified December 2003