Berge–Fulkerson coloring for C(12)‐linked permutation graphs. Issue 4 (20th July 2021)

• Record Type: Journal Article
• Authors: Liu, Siyan; Hao, Rong‐Xia; Zhang, Cun‐Quan; Zhang, Zhang
• Is Part Of: Journal of graph theory. Volume 98:Issue 4(2021)
• Page Start: 662
• Page End: 675
• Publication Date: 2021-07-20
• Subjects: Berge–Fulkerson coloring -- Berge–Fulkerson conjecture -- perfect matching -- snark; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22720
• Languages: English
• ISSNs: 0364-9024

Abstract

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.