Journal of Applied Mathematics and Physi... > Vol.3 No.12, December 2015

Yuwen Wu^1*, Yan Xia²

¹School of Information, Beijing Wuzi University, Beijing, China.
²Institute of Policy and Management, Chinese Academy of Sciences, Beijing, China.

A proper edge coloring of a graph is acyclic, if every cycle of the graph has at least 3 colors. Let r be a positive integer. An edge coloring is r-acyclic if it is proper and every cycle C has at least  colors. The r-acyclic edge chromatic   number of a graph G is the minimum number of colors needed for any r-acyclic edge coloring of G. When r=4, the result of this paper is that the 4-acyclic chromatic number of a graph with maximum degree Δ and girth  is less than 18Δ. Furthermore, if the girth of graph G is at least , then .

Girth, Edge Coloring, Acyclic Edge Coloring, Lovászlocal Lemma

Wu, Y. and Xia, Y. (2015) The 4-Acyclic Edge Coloring of Graphs with Large Girths. Journal of Applied Mathematics and Physics, 3, 1594-1598. doi: 10.4236/jamp.2015.312183.