Abstract
A proper edge coloring of a graph G is acyclic if there is no 2-colored cycle in G. The acyclic chromatic index of G is the least number of colors such that G has an acyclic edge coloring and denoted by Χ′a(G). An IC-plane graph is a topological graph where every edge is crossed at most once and no two crossed edges share a vertex. In this paper, it is proved that Χ′a(G) ≤ Δ(G) + 10, if G is an IC-planar graph without adjacent triangles and Χ′a(G) ≤ Δ(G) + 8, if G is a triangle-free IC-planar graph.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Alberson, M.O. Chromatic number, independent ratio, and crossing number. Ars Math. Contemp, 1: 1–6 (2008)
Alon, N., McDiarmid, C., Reed, B. Acyclic coloring of graphs. Random Structures Algorithms, 2: 277–288 (1991)
Alon, N., Sudakov, B., Zaks, A. Acyclic edge colorings of graphs. J. Graph Theory, 37: 157–167 (2001)
Basavaraju, M., Chandran, L.S. Acyclic edge coloring of graphs with maximum degree 4. J. Graph Theory, 61: 192–209 (2009)
Basavaraju, M., Chandran, L.S. Acyclic edge coloring of subcubic graphs. Discrete Math., 308: 6650–6653 (2008)
Bondy, J.A., Murty, U.S.R. Graph Theory with Applications. North-Holland, New York, 1976
Cohen, N., Havet, F., Müller, T. Acyclic edge-colouring of planar graphs. Extended abstract. Electron. Notes Discrete Math., 34: 417–421 (2009)
Dong, W., Xu, B. Some results on acyclic edge coloring of plane graphs. Inform. Process. Lett., 110: 887–892 (2010)
Fiamčik, J. The acyclic chromatic class of a graph (in Russian). Math. Slovaca, 28: 139–145 (1978)
Fiedorowicz, A., Haluszczak, M., Narayanan, N. About acyclic edge colourings of planar graphs. Inform. Process. Lett., 108: 412–417 (2008)
Cuan, Y., Hou, J., Yang, Y. An improved bound on acyclic chromatic index of planar graphs. Discrete Math., 313: 1098–1103 (2013)
Hou, J., Wang, W., Zhang, X. Acyclic edge coloring of planar graphs with girth at least 5. Discrete Appl. Math., 161: 2958–2967 (2013)
Hou, J., Wu, J., Liu, G., Liu, B. Acyclic edge colorings of planar graphs and series-parallel graphs. Sci. China Ser. 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)
Hou, J., Roussel, N., Wu, J. Acyclic chromatic index of planar graphs with triangles. Inform. Process. Lett., 111 (17): 836–840 (2011)
Král, D., Stacho, L. Coloring plane graphs with independent crossings. J. Graph Theory, 64(3): 184–205 (2010)
Lin, Q., Hou, J., Liu, Y. Acyclic edge coloring of graphs with large girths. Science China Mathematics, 12: 2593–2600 (2012)
Molloy, M., Reed, B. Further algorithmic aspects of the local lemma. In: Proceedings of the 30th annual ACM symposium on theory of computing, ACM, New York, 1988, 524–529
Muthu, R., Narayanan, N., Subramanian, C. Acyclic edge colouring of outerplanar graphs. Lecture Notes in Comput. Sci., 4508: 144–152 (2007)
Něsetřil, J., Wormald, N.C. The acyclic edge chromatic number of a randomd-regular graph is d + 1. J. Graph Theory, 49: 69–74 (2005)
Shu, Q., Wang, W., Wang, Y. Acyclic chromatic indices of planar graphs with girth at least 4. J. Graph Theory, 73: 386–399 (2013)
Shu, Q., Wang, W. Acyclic chromatic indices of planar graphs with girth at least five. J. Comb. Optim., 23: 140–157 (2012)
Skulrattanakulchai, S. Acyclic colorings of subcubic graphs. Inform. Process. Lett., 92: 161–167 (2004)
Song, W., Miao, L. Acyclic edge coloring of triangle-free 1-planar graphs. Acta Mathematica Sinica, English Series, 31(10): 1563–570 (2015)
Song, W., Miao, L., Li, J., Zhao, Y., Pang, J. Neighbor sum distinguishing total coloring of sparse IC-planar graphs. Discrete Applied Mathematics, 239: 183–192 (2018)
Wang, W., Shu, Q. Acyclic chromatic indices of K4-minor free graphs. Sci. China Ser. A, 41: 733–744 (2011)
Wang, W., Shu, Q., Kan, W., Wang, P. Acyclic chromatic indices of planar graphs with large girth. Discrete Appl. Math., 159: 1239–1253 (2011)
Wang, T., Zhang, Y. Acyclic edge coloring of graphs. Discrete Appl. Math., 167: 290–303 (2014)
Yu, D., Hou, J., Liu, G., Liu, B., Xu, L. Acyclic edge coloring of planar graphs with large girth. Theoret. Comput. Sci., 410: 5196–5200 (2010)
Zhang, X., Liu, G, Wu, J. Structural properties of 1-planar graphs and an application to acyclic edge coloring. Scientia Sinica Mathematica, 40: 1025–1032 (2010)
Zhang, X., Wu, J. On edge colorings of 1-planar graphs. Inform. Process. Lett., 111(3): 124–128 (2011)
Chen, J., Wang, T., Zhang, H. Acyclic Chromatic Index of Triangle-free 1-Planar Graphs, Graph and Combinatorics, 33(4): 859–868 (2017)
Acknowledgments
The authors would like to express their thanks to the referees for their valuable corrections and suggestions of the manuscript that greatly improve the format and correctness of it.
Author information
Authors and Affiliations
Corresponding authors
Additional information
This paper is supported by the National Natural Science Foundation of China (No. 11771443), Natural Science Foundation of Shandong Province (No. ZR2019BA016) and by the foundation of innovative Science and technology for youth in universities of Shandong Province (No. 2019KJI001). The work of the second author is also under the financial support from the Zaozhaung University Research Fund Project in 2019.
Rights and permissions
About this article
Cite this article
Song, Wy., Duan, Yy., Wang, J. et al. Acyclic Edge Coloring of IC-planar Graphs. Acta Math. Appl. Sin. Engl. Ser. 36, 581–589 (2020). https://doi.org/10.1007/s10255-020-0950-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10255-020-0950-3