2017/08/23 by Ting Zheng, Rong‐Xia Hao, Zheng, Ting +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1708.07122
openalex publication_date 2017/08/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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. Hagglund constructed two graphs Blowup(K4, C) and Blowup(Prism, C4). Based on these two graphs, Chen constructed infinite families of bridgeless cubic graphs M0,1,2, …,k-2, k-1 which is obtained from cyclically 4-edge-connected and having a Fulkerson-cover cubic graphs G0,G1,…, Gk-1 by recursive process. If each Gi for 1≤ i≤ k-1 is a cyclically 4-edge-connected snarks with excessive index at least 5, Chen proved that these infinite families are snarks. He obtained that each graph in M0,1,2,3 has a Fulkerson-cover and gave the open problem that whether every graph in M0,1,2, …,k-2, k-1 has a Fulkerson-cover. In this paper, we solve this problem and prove that every graph in M0,1,2, …,k-2, k-1 has a Fulkerson-cover.