The Berge-Fulkerson conjecture
This conjecture is due to Berge and Fulkerson, and appears first in [F] (see [S79b]).
If is 3-edge-colorable, then we may choose three perfect matchings so that every edge is in exactly one. Taking each of these twice gives us 6 perfect matchings with the properties described above. Thus, the above conjecture holds trivially for 3-edge-colorable graphs. There do exist bridgeless cubic graphs which are not 3-edge-colorable (for instance the Petersen graph), but the above conjecture asserts that every such graph is close to being 3-edge-colorable.
Observe that a cubic graph is a 3-graph if and only if it has no bridge. If G is an -regular graph which has an -edge-coloring, then every color class is a perfect matching, so must be even, and every color must appear in every edge-cut which separates into two sets of odd size, so every edge-cut of this form must have size at least . Thus, every -edge-colorable -regular graph is an -graph. In a sense, we may view the -graphs as the -regular graphs which have the obvious necessary conditions to be -edge-colorable. Seymour [S79b] defined -graphs and offered the following generalization of the Berge-Fulkerson conjecture.
More generally, for a graph , one may consider the vector space of real numbers indexed by . We associate every perfect matching with its characteristic vector. In this context, the Berge-Fulkerson conjecture asserts that for every 3-graph, the vector which is identically 1 may be written as a half-integer combination of perfect matchings. Edmonds matching polytope theorem [E] gives a complete characterization of what vectors in which can be written as a nonnegative real combination of perfect matchings. A particular consequence of this theorem is that the vector which is identically 1 can be written as a nonnegative rational combination of perfect matchings if G is an -graph. It follows from this that for every -graph , there is a list of perfect matchings so that every edge is contained in exactly of them. Unfortunately, the particular depends on the graph. The following weak version of the Berge-Fulkerson conjecture asserts that this dependence is inessential.
There is a fascinating theorem of Lovasz [L] that characterizes which vectors in can be written as an integer combination of perfect matchings. However, very little is known about nonnegative integer combinations of perfect matchings. In particular, if the Berge-Fulkerson conjecture is true, then for every 3-graph , there is a list of 5 perfect matchings with union (take any 5 of the 6 perfect matchings given by the conjecture). The following weakening of this (suggested by Berge) is still open.
Another consequence of the Berge-Fulkerson conjecture would be that every 3-graph has 3 perfect matchings with empty intersection (take any 3 of the 6 perfect matchings given by the conjecture). The following weakening of this (also suggested by Berge) is still open.
[E] J. Edmonds, Maximum matching and a polyhedron with 0,1-vertices, J. Res. Nat. Bur Stand B, Math & Math Phys. 69B (1965), 125-130.
[F] D.R. Fulkerson, Blocking and anti-blocking pairs of polyhedra, Math. Programming 1 (1971) 168-194. MathSciNet
[KKN] T. Kaiser, D. Kral, and S. Norine, Unions of perfect matchings in cubic graphs
[L] L. Lovasz, Matching structure and the matching lattice, J. Combin. Theory Ser. B 43 (1987), 187-222. MathSciNet
[R] R. Rizzi, Indecomposable r-graphs and some other counterexamples, J. Graph Theory 32 (1999), 1-15. MathSciNet
[S79a] P.D. Seymour, "Some unsolved problems on one-factorizations of graphs", Graph theory and Related Topics, J.A. Bondy and U.S.R. Murty (Editors), Academic, New York (1979), 367-368.
[S79b] P.D. Seymour, On multi-colourings of cubic graphs, and conjectures of Fulkerson and Tutte, Proc. London Math Soc. 38 (1979), 423-460. MathSciNet
* indicates original appearance(s) of problem.