Perfect matching covering, the Berge–Fulkerson conjecture, and the Fan–Raspaud conjecture

摘要

Let m_t~* be the largest rational number such that every bridgeless cubic graph G associated with a positive weightω has t perfect matchings {M_1, . . ., M_t } withω(∪_i~t=_1 M_i) ≥ m_t~? ω(G). It is conjectured in this paper that m_3~? = 4/5, m_4~? = 14/15, and m_5~? = 1, which are called the weighted PM-covering conjectures. The counterparts of this new invariant m?t and conjectures for unweighted cubic graphs were introduced by Kaiser et al. (2006). It is observed in this paper that the Berge–Fulkerson conjecture implies the weighted PMcovering conjectures. Each of the weighted PM-covering conjectures is further proved to imply the Fan–Raspaud conjecture. Furthermore, a 3PM-coverage index τ (respectively, τ ~? for the weighted case) is introduced for measuring the maximum ratio of the number of(respectively, the total weight of) edges covered by three perfect matchings in bridgeless cubic graphs and assessing how far a snark is from being 3-edge-colorable. It is proved that the determination of τ~ ? for bridgeless cubic graphs is an NP-complete problem