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={C1,...,Cr} be a 2-factor of G such that |Cj| is odd if and only if j2k for some integer k. The 2-factor F is C-(8)-linkedif, for every ik, there is a circuit Di of length 8 with edge sequence e1ii). 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 everyC((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. |
Year | DOI | Venue |
---|---|---|
2018 | 10.1002/jgt.22184 | JOURNAL OF GRAPH THEORY |
Keywords | Field | DocType |
Berge-Fulkerson conjecture,Berge-Fulkerson coloring,oddness,perfect matching,snarks,4-flow | Integer,Topology,Edge coloring,Graph,Discrete mathematics,Combinatorics,Cubic graph,Matching (graph theory),Conjecture,Mathematics | Journal |
Volume | Issue | ISSN |
88.0 | 1.0 | 0364-9024 |
Citations | PageRank | References |
0 | 0.34 | 15 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Rongxia Hao | 1 | 165 | 26.11 |
Cun-Quan Zhang | 2 | 496 | 69.81 |
Ting Zheng | 3 | 0 | 0.34 |