Geodesic
Acyclic chromatic index of IC-planar graphs
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 4, pp. 965-978 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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 χ_a^'(G). In this paper, we prove that χ_a^'(G)≤Δ(G)+17, for any IC-planar graph G with maximum degree Δ(G).
Keywords: acyclic chromatic index, maximum degree, IC-planar graph 
@article{DMGT_2023_43_4_a5,
     author = {Song, Wenyao and Miao, Lianying and Zhao, Yueying and Zhu, Haiyang},
     title = {Acyclic chromatic index of {IC-planar} graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {965--978},
     year = {2023},
     volume = {43},
     number = {4},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a5/}
}
TY  - JOUR
AU  - Song, Wenyao
AU  - Miao, Lianying
AU  - Zhao, Yueying
AU  - Zhu, Haiyang
TI  - Acyclic chromatic index of IC-planar graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2023
SP  - 965
EP  - 978
VL  - 43
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a5/
LA  - en
ID  - DMGT_2023_43_4_a5
ER  - 
%0 Journal Article
%A Song, Wenyao
%A Miao, Lianying
%A Zhao, Yueying
%A Zhu, Haiyang
%T Acyclic chromatic index of IC-planar graphs
%J Discussiones Mathematicae. Graph Theory
%D 2023
%P 965-978
%V 43
%N 4
%U http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a5/
%G en
%F DMGT_2023_43_4_a5
Song, Wenyao; Miao, Lianying; Zhao, Yueying; Zhu, Haiyang. Acyclic chromatic index of IC-planar graphs. Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 4, pp. 965-978. http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a5/

[1] 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

[2] 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

[3] 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

[4] 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

[5] 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

[6] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (North-Holland, New York-Amsterdam-Oxford, 1982).

[7] 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

[8] 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

[9] 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

[10] 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

[11] J. Fiamčik, The acyclic chromatic class of a graph, Math. Slovaca 28 (1978) 139–145, in Russian.

[12] 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

[13] 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

[14] 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

[15] 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

[16] 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

[17] 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

[18] 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

[19] 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

[20] 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

[21] 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

[22] 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

[23] 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

[24] 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

[25] S. Skulrattanakulchai, Acyclic colorings of subcubic graphs, Inform. Process. Lett. 92 (2004) 161–167. https://doi.org/10.1016/j.ipl.2004.08.002

[26] 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

[27] 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

[28] W. Wang and Q. Shu, Acyclic chromatic indices of K4-minor free graphs, Scientia Sin. Math. 41 (2011) 733–744. https://doi.org/10.1360/012010-530

[29] 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

[30] 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

[31] 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