A note on Berge-Fulkerson coloring

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

doi:10.1016/j.disc.2008.12.024

A note on Berge-Fulkerson coloring

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

Penn State Scranton

Research output: Contribution to journal › Article › peer-review

23 Scopus citations

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 graphG admits a Berge-Fulkerson coloring if and only if the graphG contains a pair of edge-disjoint matchingsM₁ andM₂ such that (i) M₁ ∪ M₂ induces a 2-regular subgraph ofG and (ii) the suppressed graphover(G {set minus} M_i, -), the graph obtained fromG {set minus} M_i 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 language	English (US)
Pages (from-to)	4235-4240
Number of pages	6
Journal	Discrete Mathematics
Volume	309
Issue number	13
DOIs	https://doi.org/10.1016/j.disc.2008.12.024
State	Published - Jul 6 2009

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.disc.2008.12.024

Cite this

@article{786d2e948f3c41be80bc2f22f2b318b7,

title = "A note on Berge-Fulkerson coloring",

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

author = "Rongxia Hao and Jianbing Niu and Xiaofeng Wang and Zhang, \{Cun Quan\} and Taoye Zhang",

note = "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. ",

year = "2009",

month = jul,

day = "6",

doi = "10.1016/j.disc.2008.12.024",

language = "English (US)",

volume = "309",

pages = "4235--4240",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "13",

}

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 - https://www.scopus.com/pages/publications/67349191445

UR - https://www.scopus.com/pages/publications/67349191445#tab=citedBy

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 -

A note on Berge-Fulkerson coloring

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this