The 4-Acyclic Edge Coloring of Graphs with Large Girths

DOI: 10.4236/jamp.2015.312183   PDF   HTML   XML   2,461 Downloads   2,871 Views  


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 .

Share and Cite:

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.

Conflicts of Interest

The authors declare no conflicts of interest.


[1] Alon, N., Sudakov, B. and Zaks, A. (2011) Acyclic Edge Colorings of Graphs. Journal of Graph Theory, 37, 157-167.
[2] Gerke, S., Greenhill, C. and Wormald, N. (2006) The Generalised Acyclic Edge Chromatic Number of Random Regular Graphs. Journal of Graph Theory, 52, 101-125.
[3] Gerke, S. and Raemy, M. (2007) Generalised Acyclic Edge Colourings of Graphs with Large Girth. Discrete Mathematics, 307, 1668-1671.
[4] Wu, Y.W. and Yan, G.Y. (2016) Improved Bounds on the Generalized Acyclic Chromatic Number. Acta Mathematicae Applicatae Sinica: English Series, to Appear.
[5] Bondy, J. and Murty, U. (1976) Graph Theory with Applications. MacMillan, London.
[6] Molloy, M. and Reed, B. (2002) Graph Colouring and the Probabilistic Method. Algorithms and Combinatorics. Springer, Berlin.

comments powered by Disqus

Copyright © 2020 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.