| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4649628 | Discrete Mathematics | 2009 | 6 Pages |
The Berge–Fulkerson Conjecture states that every cubic bridgeless graph has six perfect matchings such that every edge of the graph is contained in exactly two of these perfect matchings. In this paper, a useful technical lemma is proved that a cubic graph GGadmits a Berge–Fulkerson coloring if and only if the graph GGcontains a pair of edge-disjoint matchings M1M1and M2M2 such that (i) M1∪M2M1∪M2induces a 2-regular subgraph of GG and (ii) the suppressed graph G∖Mi¯, the graph obtained from G∖MiG∖Miby suppressing all degree-2-vertices, is 3-edge-colorable for each i=1,2i=1,2. This lemma is further applied in the verification of Berge–Fulkerson Conjecture for some families of non-3-edge-colorable cubic graphs (such as, Goldberg snarks, flower snarks).
