Perfect Matchings in Cubic Graphs that have Empty Intersection
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
Berg and independently Fulkerson fulker.htm
conjectured that every bridgeless cubic graph has a collection of six
perfect matchings that together contain every edge exactly twice. No
edge is in three of these matchings.
Conjecture: There exists a k such that every
bridgeless cubic graph has a collection of k perfect matchings
such that no edge is in every matching.
For a related problem see covmatch.html.
[F] D.R. Fulkerson, Blocking and anti-blocking pairs of polyhedra, Math. Programming 1 (1971) 168-194.
Submitted by: Dan Archdeacon, Department of Mathematics and
Statistics, University of Vermont, Burlington VT 05405 USA. (With
thanks to Matt Devos)
Send comments to email@example.com