TY - JOUR
T1 - A note on Berge-Fulkerson coloring
AU - Hao, Rongxia
AU - Niu, Jianbing
AU - Wang, Xiaofeng
AU - Zhang, Cun Quan
AU - Zhang, Taoye
N1 - Funding Information:
The first author was supported by the Natural Science Foundation of China (under the Grant Number 10871021).
Funding Information:
The fourth author was partially supported by the National Security Agency under Grant MSPR-03G-023.
PY - 2009/7/6
Y1 - 2009/7/6
N2 - 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 graphG admits a Berge-Fulkerson coloring if and only if the graphG contains a pair of edge-disjoint matchingsM1 andM2 such that (i) M1 ∪ M2 induces a 2-regular subgraph ofG and (ii) the suppressed graphover(G {set minus} Mi, -), the graph obtained fromG {set minus} Mi by 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).
AB - 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 graphG admits a Berge-Fulkerson coloring if and only if the graphG contains a pair of edge-disjoint matchingsM1 andM2 such that (i) M1 ∪ M2 induces a 2-regular subgraph ofG and (ii) the suppressed graphover(G {set minus} Mi, -), the graph obtained fromG {set minus} Mi by 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).
UR - http://www.scopus.com/inward/record.url?scp=67349191445&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=67349191445&partnerID=8YFLogxK
U2 - 10.1016/j.disc.2008.12.024
DO - 10.1016/j.disc.2008.12.024
M3 - Article
AN - SCOPUS:67349191445
SN - 0012-365X
VL - 309
SP - 4235
EP - 4240
JO - Discrete Mathematics
JF - Discrete Mathematics
IS - 13
ER -