An acyclic edge coloring of a graph $ G $ is a proper edge coloring such that no bichromatic cycles are produced. The acyclic chromatic index of $ G $, denoted by $ \chi^{'}_{a}(G) $, is the smallest integer $ k $ such that $ G $ is acyclically edge $ k $-colorable. In this paper, we consider the planar graphs without 3-cycles and intersecting 4-cycles, and prove that $ \chi^{'}_{a}(G)\leq\Delta(G)+1 $ if $ \Delta(G)\geq 8 $.
Citation: Yuehua Bu, Qi Jia, Hongguo Zhu, Junlei Zhu. Acyclic edge coloring of planar graphs[J]. AIMS Mathematics, 2022, 7(6): 10828-10841. doi: 10.3934/math.2022605
An acyclic edge coloring of a graph $ G $ is a proper edge coloring such that no bichromatic cycles are produced. The acyclic chromatic index of $ G $, denoted by $ \chi^{'}_{a}(G) $, is the smallest integer $ k $ such that $ G $ is acyclically edge $ k $-colorable. In this paper, we consider the planar graphs without 3-cycles and intersecting 4-cycles, and prove that $ \chi^{'}_{a}(G)\leq\Delta(G)+1 $ if $ \Delta(G)\geq 8 $.
| [1] |
N. Alon, C. McDiarmid, B. Reed, Acyclic coloring of graphs, Random Struct. Algor., 2 (1991), 277–288. http://dx.doi.org/10.1002/rsa.3240020303 doi: 10.1002/rsa.3240020303
|
| [2] |
M. Basavaraju, L. Chandran, N. Cohen, F. Havet, T. M$\ddot{u}$lle, Acyclic edge-coloring of planar graphs, SIAM J. Discrete Math., 25 (2011), 463–478. http://dx.doi.org/10.1137/090776676 doi: 10.1137/090776676
|
| [3] | J. Fiam$\check{c}$ik, The acyclic chromatic class of a graph(Russian), Math. Slovaca, 28 (1978), 139–145. |
| [4] |
P. Fialho, B. de Lima, A. Procacci, A new bound on the acyclic edge chromatic number, Discrect Math., 343 (2020), 112037. http://dx.doi.org/10.1016/j.disc.2020.112037 doi: 10.1016/j.disc.2020.112037
|
| [5] |
A. Fiedorowicz, Acyclic edge colouring of plane graphs, Discrete Appl. Math., 160 (2012), 1513–1523. http://dx.doi.org/10.1016/j.dam.2012.02.018 doi: 10.1016/j.dam.2012.02.018
|
| [6] |
J. Hou, W. Wang, X. Zhang, Acyclic edge coloring of planar graphs with girth at least 5, Discrete Appl. Math., 161 (2013), 2958–2967. http://dx.doi.org/10.1016/j.dam.2013.06.013 doi: 10.1016/j.dam.2013.06.013
|
| [7] | L. Kirousis, J. Livieratos, The acyclic chromatic index is less than the double of the max degree, arXiv: 1901.07856v6. http://dx.doi.org/10.48550/arXiv.1901.07856 |
| [8] |
M. Molloy, B. Reed, Further algorithmic aspects of the local lemma, Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Comouting, 1998,524–529. http://dx.doi.org/10.1145/276698.276866 doi: 10.1145/276698.276866
|
| [9] |
W. Wang, Q. Shu, Y. Wang, A new upper bound on the acyclic chromatic indices of planar graphs, Eur. J. Combin., 34 (2013), 338–354. http://dx.doi.org/10.1016/j.ejc.2012.07.008 doi: 10.1016/j.ejc.2012.07.008
|
| [10] |
T. Wang, Y. Zhang, Further result on acyclic chromatic index of planar graphs, Discrete Appl. Math., 201 (2016), 228–247. http://dx.doi.org/10.1016/j.dam.2015.07.015 doi: 10.1016/j.dam.2015.07.015
|
| [11] |
Q. Shu, W. Wang, Y. Wang, Acyclic chromatic indices of planar graphs with girth at least 4, J. Graph Theory, 73 (2013), 386–399. http://dx.doi.org/10.1002/jgt.21683 doi: 10.1002/jgt.21683
|
| [12] | Q. Shu, Y. Chen, S. Han, G. Lin, E. Miyano, A. Zhang, Acyclic edge coloring conjecture is true on planar graphs without intersecting triangles, Theor. Comput. Sci., 882 (2021), 77–108. http://dx.doi.org/j.tcs.2021.06.017 |
| [13] |
Y. Wang, P. Sheng, Improved upper bound for acyclic chromatic index of planar graphs without 4-cycles, J. Comb. Optim., 27 (2014), 519–529. http://dx.doi.org/10.1007/s10878-012-9524-5 doi: 10.1007/s10878-012-9524-5
|
| [14] |
W. Wang, Q. Shu, Y. Wang, Acyclic edge coloring of planar graphs without 4-cycles, J. Comb. Optim., 25 (2013), 562–586. http://dx.doi.org/10.1007/s10878-012-9474-y doi: 10.1007/s10878-012-9474-y
|
Figures(3)
Yuehua Bu, Qi Jia, Hongguo Zhu, Junlei Zhu. Acyclic edge coloring of planar graphs[J]. AIMS Mathematics, 2022, 7(6): 10828-10841. doi: 10.3934/math.2022605
DownLoad: