Berge–Fulkerson coloring for C(8)‐linked graphs. Issue 1 (8th September 2017) - Hao, Rong‐Xia; Zhang, Cun‐Quan; Zheng, Ting
Abstract: 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 . Let G be a cubic graph and F = C 1, …, C r be a 2‐factor of G such that | C j | is odd if and only if j ≤ 2 k for some integer k . The 2‐factor F is C (8) ‐linked if, for every i ≤ k, there is a circuit D i of length 8 with edge sequence e 1 i … e 8 i where e 1 i, e 5 i ∈ E ( C 2 i − 1 ) and e 3 i, e 7 i ∈ E ( C 2 i ) . And the cubic graph G is C (8) ‐linked if it contains a C (8) ‐linked 2‐factor. It is proved in this article that every C (8) ‐linked cubic graph is Berge–Fulkerson colorable . It is also noticed that many classical families of snarks (including some high oddness snarks) are C (8) ‐linked. Consequently, the Berge–Fulkerson conjecture is verified for these infinite families of snarks.