Acyclic Edge Coloring of 4-Regular Graphs Without 3-Cycles

• DOI: 10.1007/s40840-017-0484-x
• Publication Date: 2017-04-09T15:14:00Z
• Authors: Qiaojun Shu; Yiqiao Wang; Yulai Ma; Weifan Wang
• Keywords: Edge Coloring

A proper edge coloring is called acyclic if no bichromatic cycles are produced. It was conjectured that every simple graph G with maximum degree $$\varDelta $$ is acyclically edge- $$(\varDelta +2)$$ -colorable. Basavaraju and Chandran (J Graph Theory 61:192–209, 2009) confirmed the conjecture for non-regular graphs G with $$\varDelta =4$$ . In this paper, we extend this result by showing that every 4-regular graph G without 3-cycles is acyclically edge-6-colorable.