Abstract
A proper edge coloring of a graph G is called acyclic if there is no 2-colored cycle in G. The acyclic edge chromatic number of G, denoted by a′(G), is the least number of colors in an acyclic edge coloring of G. Alon et al. conjectured that a′(G) ≤ Δ(G) + 2 for any graphs. In this paper, it is shown that the conjecture holds for planar graphs without 4- and 5-cycles or without 4- and 6-cycles.
Similar content being viewed by others
References
Alon N.: A parallel algorithmic version of the Local Lemma. Random Struct. Algorithms 2, 367–378 (1991)
Alon N., Sudakov B., Zaks A.: Acyclic edge colorings of graphs. J. Graph Theory 37, 157–167 (2001)
Alon N., Zaks A.: Algorithmic aspects of acyclic edge colorings. Algorithmica 32, 611–614 (2002)
Basavaraju M., Chandran L.S.: Acyclic edge coloring of subcubic graphs. Discret. Math. 308, 6650–6653 (2008)
Borodin O.V.: On acyclic colorings of planar graphs. Discret. Math. 25, 211–236 (1979)
Burnstein, M.I.: Every 4-valent graph has an acyclic 5-coloring (in Russian), Soobšč Akad Nauk Gruzin SSR 93, 21–24 (1979) (Georgian and English summaries)
Fiedorowicz A., Hałuszczak M., Narayanan N.: About acyclic edge colourings of planar graphs. Inform. Process. Lett. 108, 412–417 (2008)
Grü B.: Acyclic colorings of planar graphs. Israel J. Math. 14, 390–408 (1973)
Hou J., Liu G., Wang G.: Improved bounds for acyclic chromatic index of planar graphs. Discret. Appl. Math. 159, 876–881 (2011)
Hou J., Wu J., Liu G., Liu B.: Acyclic edge colorings of planar graphs and series-parallel graphs. Sci. Chin. A 52, 605–616 (2009)
Hou J., Wu J., Liu G., Liu B.: Acyclic edge chromatic number of outerplanar graphs. J. Graph Theory 64, 22–36 (2010)
Kostochka A.K., Mel’nikov L.S.: Note to the paper of Grünbaum on acyclic colorings. Discret. Math. 14, 403–406 (1976)
Molloy, M., Reed, B.: Further Algorithmic Aspects of the Local Lemma. In: Proceedings of the 30th annual ACM Symposium on theory of computing, 524–529 (1998)
Muthu R., Narayanan N., Subramanian C.R.: Optimal acyclic edge colouring of grid like graphs. Lect. Notes Comp. Sci. 4112, 360–367 (2006)
Muthu R., Narayanan N., Subramanian C.R.: Acyclic edge colouring of outerplanar graphs. Lect. Notes Comp. Sci. 4508, 144–152 (2007)
Skulrattanakulchai S.: Acyclic colorings of subcubic graphs. Inform. Process. Lett. 92, 161–167 (2004)
Yu D., Hou J., Liu G., Liu B., Xu L.: Acyclic edge coloring of planar graphs with large girth. Theor. Comp. Sci. 410, 5196–5200 (2009)
Author information
Authors and Affiliations
Corresponding author
Additional information
This work is supported by research grants NSFC (11001055, 10871119, 10631070, 10971121), NSFFP (2010J05004) and NSFSP (ZR2009AM009).
Rights and permissions
About this article
Cite this article
Hou, J., Liu, G. & Wu, J. Acyclic Edge Coloring of Planar Graphs Without Small Cycles. Graphs and Combinatorics 28, 215–226 (2012). https://doi.org/10.1007/s00373-011-1043-0
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00373-011-1043-0