The acyclic chromatic index of planar graphs without 4-, 6-cycles and intersecting triangles

Abstract

A proper edge k-coloring is a mapping \varphi :E\left(G\right)\to \{1,2,\dots ,k\} such that any two adjacent edges receive different colors. A proper edge k-coloring \varphi of G is called acyclic if there are no bichromatic cycles in G. The acyclic chromatic index of G, denoted by {\chi }_a^{\prime }\left(G\right), is the smallest integer k such that G is acyclically edge k-colorable. In this paper, we show that if G is a plane graph without 4-, 6-cycles and intersecting 3-cycles, \mathrm{\Delta }\left(G\right)\ge 9, then \begin{array}{c}{\chi }_a^{\prime }\left(G\right)\le \mathrm{\Delta }\left(G\right)+1\hfill \end{array}.

Keywords

Acyclic edge coloring / plane graph / cycle

References

[1] Alon N, McDiarmid C, Reed B. Acyclic coloring of graphs. Random Structures Algorithms 1991; 2(3): 277–288

[2] Basavaraju M, Chandran L S, Cohen N, Havet F, Mülle T. Acyclic edge-coloring of planar graphs. SIAM J Discrete Math 2011; 25(2): 463–478

[3] Fialho P M S, de Lima B N B, Procacci A. A new bound on the acyclic edge chromatic number. Discrete Math 2020; 343(11): 112037

[4] Fiamčík J. The acyclic chromatic class of a graph. Math. Slovaca 1978; 28(2): 139–145

[5] Hou J F, Liu G Z, Wu J L. Acyclic edge coloring of planar graphs without small cycles. Graphs Combin 2012; 28(2): 215–226

[6] Hou J F, Wang W T, Zhang X R. Acyclic edge coloring of planar graphs with girth at least 5. Discrete Appl Math 2013; 161(18): 2958–2967

[7] Hudák D, Kardoš F, Lužar B, Soták R, Škrekovski R. Acyclic edge coloring of planar graphs with ∆ colors. Discrete Appl Math 2012; 160(9): 1356–1368

[8] KirousisLLivieratosJ. The acyclic chromatic index is less than the double of the max degree. 2022, arXiv: 1901.07856v7

[9] MolloyMReedB. Further algorithmic aspects of the local lemma, In: STOC ’98 (Dallas, TX). New York: ACM, 1999, 524−529

[10] Shu Q J, Chen Y, Han S G, Lin G H, Miyano E, Zhang A. Acyclic edge coloring conjecture is true on planar graphs without intersecting triangles. Theoret Comput Sci 2021; 882: 77–108

[11] Shu Q J, Wang W F, Wang Y Q. Acyclic edge coloring of planar graphs without 5-cycles. Discrete Appl Math 2012; 160(7/8): 1211–1223

[12] Shu Q J, Wang W F, Wang Y Q. Acyclic chromatic indices of planar graphs with girth at least 4. J Graph Theory 2013; 73(4): 386–399

[13] Wang T, Zhang Y Q. Further result on acyclic chromatic index of planar graphs. Discrete Appl Math 2016; 201: 228–247

[14] Wang W F, Shu Q J, Wang K, Wang P. Acyclic chromatic indices of planar graphs with large girth. Discrete Appl Math 2011; 159(12): 1239–1253

[15] Wang W F, Shu Q J, Wang Y Q. A new upper bound on the acyclic chromatic indices of planar graphs. European J Combin 2013; 34(2): 338–354

[16] Wang W F, Shu Q J, Wang Y Q. Acyclic edge coloring of planar graphs without 4-cycles. J Comb Optim 2013; 25(4): 562–586

[17] Wang Y Q, Shu Q J. Acyclic edge coloring of planar graphs. J Jiangsu Norm Univ (Nat Sci Ed) 2014; 32(3): 22–26

[18] Wang Y Q, Shu Q J, Wang W F. The acyclic edge coloring of planar graphs without a 3-cycle adjacent to a 4-cycle. Discrete Appl Math 2013; 161(16/17): 2687–2694

[19] Wang Y Q, Shu Q J, Wu J L, Zhang W W. Acyclic edge coloring of planar graphs without a 3-cycle adjacent to a 6-cycle. J Comb Optim 2014; 28(3): 692–715

[20] Wang Y Q, Sheng P. Improved upper bound for acyclic chromatic index of planar graphs without 4-cycles. J Comb Optim 2014; 27(3): 519–529

[21] Xie D Z, Wu Y Q. Acyclic edge coloring of planar graphs without adjacent triangles. J Math Res Appl 2012; 32(4): 407–414

RIGHTS & PERMISSIONS

Higher Education Press 2024