Berge–Fulkerson Conjecture, Perfect Matching Partial Coverings and Odd Dividers

It is conjectured by Berge and Fulkerson that every bridgeless cubic graph has six perfect matchings such that each edge is contained in exactly two of them. The Fan‐Raspaud conjecture, implied by the Berge‐Fulkerson conjecture, holds for all graphs of oddness two due to Máčajová and Škoviera (Combinatorica [2014]). An interesting problem is to investigate the validity of the Berge‐Fulkerson conjecture for graphs of oddness two, especially permutation graphs. In this study, we propose a new approach to the Berge–Fulkerson conjecture by finding a relationship between the conjecture and perfect matching partial coverings. As applications of the main results, the conjecture is confirmed for permutation graphs containing an ‐alternating circuit of length at most 16, which improves early results about ‐alternating circuits of length 8 and 12.