A note on Berge-Fulkerson coloring

作者：Hao Rongxia; Niu Jianbing; Wang Xiaofeng; Zhang Cun Quan^*; Zhang Taoye

来源：Discrete Mathematics, 2009, 309(13): 4235-4240.

DOI：10.1016/j.disc.2008.12.024

• Fulkerson coloring
• Snark
• Edge-coloring
• Cubic graph
• Perfect matching

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 graph G admits a Berge-Fulkerson coloring if and only if the graph G contains a pair of edge-disjoint matchings M-1 and M-2 such that (i) M-1 boolean OR M-2 induces a 2-regular subgraph of G and (ii) the suppressed graph G \ M-i, the graph obtained from G \ M-i by suppressing all degree-2-vertices, is 3-edge-colorable for each i = 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).

• 出版日期2009-7-6
• 单位北京交通大学