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 -