|
|||||
|
|
A note on Berge-Fulkerson coloring |
|
| Authors: | Rongxia Hao Xiaofeng Wang Taoye Zhang |
| Institution: | a Department of Mathematics, Beijing Jiaotong University, Beijing 100044, China b Department of Mathematics, Tennessee Wesleyan College, Athens, TN 37371, United States c Department of Mathematics, West Virginia University, Morgantown, WV 26506-6310, United States d Department of Mathematics, Penn State University, Worthington, PA 18512, United States |
| Abstract: | The Berge-Fulkerson Conjecture states that every cubic bridgeless graph has six perfect matchings such that every edge of the graph is contained in exactly two of these perfect matchings. In this paper, a useful technical lemma is proved that a cubic graphGadmits a Berge-Fulkerson coloring if and only if the graphGcontains a pair of edge-disjoint matchingsM1andM2 such that (i) M1∪M2induces a 2-regular subgraph ofG and (ii) the suppressed graph , the graph obtained fromG?Miby suppressing all degree-2-vertices, is 3-edge-colorable for eachi=1,2. This lemma is further applied in the verification of Berge-Fulkerson Conjecture for some families of non-3-edge-colorable cubic graphs (such as, Goldberg snarks, flower snarks). |
| Keywords: | Fulkerson coloring Snark Edge-coloring Cubic graph Perfect matching |
| 本文献已被 ScienceDirect 等数据库收录！ | |