Originators: Fan & Raspaud, Bonisoli & Cariolaro (presented by D. West - REGS 2010)
Definitions: A cut-edge in a graph is an edge whose deletion increases the number of components. When a 3-regular graph has a perfect matching, deleting it leaves a 2-factor (a 2-regular spanning subgraph; every component is a cycle).
Background: The Berge-Fulkerson Conjecture (BFC), posed in 1971, states that every 3-regular graph with no cut-edge has six matchings such that every edge appears in exactly two of them. The BFC holds trivially for 3-regular graphs that are 3-edge-colorable; take each color class of a proper 3-edge-coloring twice. (See (Archdeacon or Mohar for further discussion of the BFC.) It remains unknown whether various statements implied by the BFC are true; they might be easier to prove than the full strength of the conjecture.
Conjecture 1: (Fan-Raspaud [FR]) Every 3-regular graph with no cut-edge has three perfect matchings such that no edge appears in all three of them.
Conjecture 2: (Bonisoli-Cariolaro [BC]) Every 3-regular graph with no cut-edge has five perfect matchings such that every edge appears in at least one of them.
Comments: Both conjectures follow immediately from the BFC. For Conjecture 1, take any three of the six matchings guarantee by the BFC; for Conjecture 2, take any five of them. For Conjecture 2, no example other than the Petersen graph is known to need five perfect matchings, so the stronger conclusion that the Petersen graph is the only example needing at least five perfect matchings could be true. The question makes sense, since a standard strengthening of Petersen's Theorem shows that every edge of a 3-regular graph having no cut-edge appears in some perfect matching.
This minimum number of perfect matchings to cover the edges contrasts with the edge-chromatic number χ′(G). Vizing [V] proved that χ′(G)≤Δ(G)+1, but Bonisoli-Cariolaro [BC] constructed regular graphs where the difference between χ′(G) and the number of perfect matchings needed to cover the edges is arbitrarily large (and finite).
Question 3: (West) What is the smallest k such that every n-vertex graph in which every edge appears in some perfect matching can be covered by k perfect matchings?
Comments: Let r be odd, and let n=2r. Let G be the (r-1)-regular n-vertex graph obtained from two disjoint copies of Kr by deleting one edge from each and replacing them with two edges joining the components. In G, every perfect matching contains exactly one of the two added edges. Therefore, distinct perfect matchings are needed to cover the 2r-4 edges incident to their endpoints in one of the two original complete graphs. Hence the answer to Question 3 is at least n-4. ***There may be a construction known that needs slightly more, but nothing as big as n.
The oddness of a 3-regular graph G having a perfect matching is the minimum number of components with odd length in a 2-factor of G. If G is 3-edge-colorable, then deleting one color class from a proper 3-edge-coloring leaves a 2-factor with no odd component; hence G has oddness 0 if and only if G is 3-edge-colorable. Macajova-Skoviera [MS] proved that the Fan-Raspaud Conjecture is true for 3-regular graphs with oddness at most 2. One can seek further partial results toward these conjectures by bounding the oddness of the graphs considered.
Question 4: Does the Fan-Raspaud Conjecture hold for 3-regular graphs with oddness 4? Does the BFC hold for 3-regular graphs with oddness 2? Does the Bonisoli-Cariolaro Conjecture hold for 3-regular graphs with oddness 2?
References:
to be completed
[BC] Bonisoli and D. Cariolaro 2007, Ars Combinatoria.
[FR] G. Fan and A. Raspaud, 1994.
[MS] E. Macajova and M. Skoviera, 2009.
[MY] Mazzuocolo and M. Young.