A note on Berge-Fulkerson coloring

Rongxia Hao, Jianbing Niu, Xiaofeng Wang, Cun Quan Zhang, Taoye Zhang

Research output: Contribution to journalArticlepeer-review

20 Scopus citations


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).

Original languageEnglish (US)
Pages (from-to)4235-4240
Number of pages6
JournalDiscrete Mathematics
Issue number13
StatePublished - Jul 6 2009

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'A note on Berge-Fulkerson coloring'. Together they form a unique fingerprint.

Cite this