Berge–Fulkerson coloring for C(12)‐linked permutation graphs. Issue 4 (20th July 2021) - Liu, Siyan; Hao, Rong‐Xia; Zhang, Cun‐Quan; Zhang, Zhang
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 permutation graph with a 2‐factor F = { C 1, C 2 } . A circuit C 0 is F ‐alternating if E ( C 0 ) ⧹ ( E ( C 1 ) ∪ E ( C 2 ) ) is a perfect matching of C 0 . A permutation graph G with a 2‐factor F = { C 1, C 2 } is C ( 12 ) ‐linked if it contains an F ‐alternating circuit of length at most 12. It is proved in this paper that every C ( 12 ) ‐ linked permutation graph is Berge–Fulkerson colorable . As an application, the conjecture is verified for some families of snarks constructed by Abreu et al., Brinkmann et al., and Hägglund et al.