Article in volume
Authors:
Wenyao Song
School of Mathematics and Statistics, Zaozhuang University, Zaozhuang 277160, China
email: songwenyao@cumt.edu.cn
Yueying Zhao
School of Mathematics, China University of Mining and Technology
email: zlyue2006@126.com
Haiyang Zhu
Department of Flight Support Command, Air Force Logistics College, Xuzhou 221000 , China
email: tulunzhuhaiyang7@126.com
Title:
Acyclic chromatic index of IC-planar graphs
PDFSource:
Discussiones Mathematicae Graph Theory 43(4) (2023) 965-978
Received: 2017-09-08 , Revised: 2020-04-18 , Accepted: 2021-05-16 , Available online: 2023-02-21 , https://doi.org/10.7151/dmgt.2487
Abstract:
Two distinct crossings are independent if the end-vertices of any two pairs of
crossing edges are disjoint. If a graph $G$ has a drawing in the plane such that
every two crossings are independent, then we call $G$ a plane graph with
independent crossings or IC-planar graph for short. 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 $\chi'_{a}(G)$. In this paper, we prove
that $\chi'_{a}(G)\leq\Delta(G)+17$, for any IC-planar graph $G$ with maximum
degree $\Delta(G)$.
Keywords:
acyclic chromatic index, maximum degree, IC-planar graph
References:
- M.O. Alberson, Chromatic number, independent ratio, and crossing number, Ars Math. Contemp. 1 (2008) 1–6.
https://doi.org/10.26493/1855-3974.10.2d0 - N. Alon, C. McDiarmid and B. Reed, Acyclic coloring of graphs, Random Structures Algorithms 2 (1991) 277–288.
https://doi.org/10.1002/rsa.3240020303 - N. Alon, B. Sudakov and A. Zaks, Acyclic edge colorings of graphs, J. Graph Theory 37 (2001) 157–167.
https://doi.org/10.1002/jgt.1010 - M. Basavaraju and L.S. Chandran, Acyclic edge coloring of subcubic graphs, Discrete Math. 308 (2008) 6650–6653.
https://doi.org/10.1016/j.disc.2007.12.036 - M. Basavaraju and L.S. Chandran, Acyclic edge coloring of graphs with maximum degree $4$, J. Graph Theory 61 (2009) 192–209.
https://doi.org/10.1002/jgt.20376 - J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (North-Holland, New York-Amsterdam-Oxford, 1982).
- J. Chen, T. Wang and H. Zhang, Acyclic chromatic index of triangle-free $1$-planar graphs, Graphs Combin. 33 (2017) 859–868.
https://doi.org/10.1007/s00373-017-1809-0 - N. Cohen, F. Havet and T. Müller, Acyclic edge-colouring of planar graphs. Extended abstract, Electron. Notes Discrete Math. 34 (2009) 417–421.
https://doi.org/10.1016/j.endm.2009.07.069 - W. Dong and B. Xu, Some results on acyclic edge coloring of plane graphs, Inform. Process. Lett. 110 (2010) 887–892.
https://doi.org/10.1016/j.ipl.2010.07.019 - L. Esperet and A. Parreau, Acyclic edge-coloring using entropy compression, European J. Combin. 34 (2013) 1019–1027.
https://doi.org/10.1016/j.ejc.2013.02.007 - J. Fiamčik, The acyclic chromatic class of a graph, Math. Slovaca 28 (1978) 139–145, in Russian.
- A. Fiedorowicz, M. Hałuszczak and N. Narayanan, About acyclic edge colourings of planar graphs, Inform. Process. Lett. 108 (2008) 412–417.
https://doi.org/10.1016/j.ipl.2008.07.016 - I. Giotis, L. Kirousis, K.I. Psaromiligkos and D.M. Thilikos, Acyclic edge coloring through the Lovász Local Lemma, Theoret. Comput. Sci. 665 (2017) 40–50.
https://doi.org/10.1016/j.tcs.2016.12.011 - J.F. Hou, N. Roussel and J. Wu, Acyclic chromatic index of planar graphs with triangles, Inform. Process. Lett. 111 (2011) 836–840.
https://doi.org/10.1016/j.ipl.2011.05.023 - J. Hou, J. Wu, G. Liu and B. Liu, Acyclic edge colorings of planar graphs and series-parallel graphs, Sci. China Ser. A 52 (2009) 605–616.
https://doi.org/10.1007/s11425-008-0124-x - J. Hou, J. Wu, G. Liu and B. Liu, Acyclic edge chromatic number of outerplanar graphs, J. Graph Theory 64 (2010) 22–36.
https://doi.org/10.1002/jgt.20436 - D. Král and L. Stacho, Coloring plane graphs with independet crossings, J. Graph Theory 64 (2010) 184–205.
https://doi.org/10.1002/jgt.20448 - M. Molloy and B. Reed, Further algorithmic aspects of the local lemma, in: Proc. 30th Annual ACM Symposium on Theory of Computing, (ACM, New York 1998) 524–529.
https://doi.org/10.1145/276698.276866 - R. Muthu, N. Narayanan and C.R. Subramanian, Acyclic edge colouring of outerplanar graphs, Lecture Notes in Comput. Sci. 4508 (2007) 144–152.
https://doi.org/10.1007/978-3-540-72870-2_14 - R. Muthu, N. Narayanan and C.R. Subramanian, Improved bounds on acyclic edge colouring, Discrete Math. 307 (2007) 3063–3069.
https://doi.org/10.1016/j.disc.2007.03.006 - S. Ndreca, A. Procacci and B. Scoppola, Improved bounds on coloring of graphs, European J. Combin. 33 (2012) 592–609.
https://doi.org/10.1016/j.ejc.2011.12.002 - J. Něsetřil and N.C. Wormald, The acyclic edge chromatic number of a random d-regular graph is $d+1$, J. Graph Theory 49 (2005) 69–74.
https://doi.org/10.1002/jgt.20064 - Q. Shu and W. Wang, Acyclic chromatic indices of planar graphs with girth at least five, J. Comb. Optim. 23 (2012) 140–157.
https://doi.org/10.1007/s10878-010-9354-2 - Q. Shu, W. Wang and Y. Wang, Acyclic chromatic indices of planar graphs with girth at least $4$, J. Graph Theory 73 (2013) 386–399.
https://doi.org/10.1002/jgt.21683 - S. Skulrattanakulchai, Acyclic colorings of subcubic graphs, Inform. Process. Lett. 92 (2004) 161–167.
https://doi.org/10.1016/j.ipl.2004.08.002 - W.Y. Song and L.Y. Miao, Acyclic edge coloring of triangle-free $1$-planar graphs, Acta Mat. Sin. (Engl. Ser.) 31 (2015) 1563–1570.
https://doi.org/10.1007/s10114-015-4479-y - T. Wang and Y. Zhang, Acyclic edge coloring of graphs, Discrete Appl. Math. 167 (2014) 290–303.
https://doi.org/10.1016/j.dam.2013.12.001 - W. Wang and Q. Shu, Acyclic chromatic indices of $K_{4}$-minor free graphs, Scientia Sin. Math. 41 (2011) 733–744.
https://doi.org/10.1360/012010-530 - W. Wang, Q. Shu, K. Wang and P. Wang, Acyclic chromatic indices of planar graphs with large girth, Discrete Appl. Math. 159 (2011) 1239–1253.
https://doi.org/10.1016/j.dam.2011.03.017 - D. Yu, J. Hou, G. Liu, B. Liu and L. Xu, Acyclic edge coloring of planar graphs with large girth, Theoret. Comput. Sci. 410 (2009) 5196-5200.
https://doi.org/10.1016/j.tcs.2009.08.015 - X. Zhang, G. Liu and J. Wu, Structural properties of $1$-planar graphs and an application to acyclic edge coloring, Scientia Sin. Math. 40 (2010) 1025–1032.
https://doi.org/10.1360/012009-678
Close