Unique Fulkerson coloring of Petersen minor-free cubic graphs

作者：Miao Zhengke^*; Wang Xiaofeng; Zhang Cun Quan

来源：European Journal of Combinatorics, 2015, 43: 165-171.

DOI：10.1016/j.ejc.2014.08.021

Let G be a cubic graph and the graph 2G is obtained by replacing each edge of G with a pair of parallel edges. A proper 6-edge-coloring of 2G is called a Fulkerson coloring of G. It was conjectured by Fulkerson that every bridgeless cubic graph has a Fulkerson coloring. In this paper we show that for a Petersen-minor free Graph G, G is uniquely Fulkerson colorable if and only if G constructed from K-4 via a series of Y - Delta-operations (expending a vertex by a triangle). This theorem is a partial result to the conjecture that, for a Petersenminor free Graph G, G is uniquely 3-edge-colorable if and only if G constructed from K-4 via a series of Y - Delta-operations (expending a vertex by a triangle).

• 出版日期2015-1