Unique Fulkerson coloring of Petersen minor-free cubic graphs. (January 2015)

• Record Type: Journal Article
• Authors: Miao, Zhengke; Wang, Xiaofeng; Zhang, Cun-Quan
• Is Part Of: European journal of combinatorics. Volume 43(2015:Jan.)
• Page Start: 165
• Page End: 171
• Publication Date: 2015-01
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2014.08.021
• Languages: English
• ISSNs: 0195-6698

Abstract

Abstract: Let G be a cubic graph and the graph 2 G is obtained by replacing each edge of G with a pair of parallel edges. A proper 6 -edge-coloring of 2 G 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 − Δ -operations (expending a vertex by a triangle). This theorem is a partial result to the conjecture that, for a Petersen-minor free Graph G, G is uniquely 3 -edge-colorable if and only if G constructed from K 4 via a series of Y − Δ -operations (expending a vertex by a triangle).