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

doi:10.3868/s140-DDD-024-0003-x

Front. Math. China

2024, Vol. 19

Issue (3) : 117-136 https://doi.org/10.3868/s140-DDD-024-0003-x

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

Yuehua BU^1,², Qi JIA¹, Hongguo ZHU¹(

)

¹. College of Mathematics and Computer Science, Zhejiang Normal University, Jinhua 321004, China
². Xingzhi College, Zhejiang Normal University, Jinhua 321004, China

Download: PDF(926 KB) HTML
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

Abstract

A proper edge k-coloring is a mapping $ϕ : E (G) → {1, 2, …, k}$ such that any two adjacent edges receive different colors. A proper edge k-coloring $ϕ$ of G is called acyclic if there are no bichromatic cycles in G. The acyclic chromatic index of G, denoted by $χ a ′ (G)$ , 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, $Δ (G) ≥ 9$ , then $χ a ′ (G) ≤ Δ (G) + 1$ .

Keywords Acyclic edge coloring plane graph cycle

Corresponding Author(s): Hongguo ZHU

Online First Date: 18 June 2024 Issue Date: 01 July 2024

Cite this article:

Yuehua BU,Qi JIA,Hongguo ZHU. The acyclic chromatic index of planar graphs without 4-, 6-cycles and intersecting triangles[J]. Front. Math. China, 2024, 19(3): 117-136.

URL:

https://academic.hep.com.cn/fmc/EN/10.3868/s140-DDD-024-0003-x
https://academic.hep.com.cn/fmc/EN/Y2024/V19/I3/117

1	N Alon, C McDiarmid, B Reed. Acyclic coloring of graphs. Random Structures Algorithms 1991; 2(3): 277–288
2	M Basavaraju, L S Chandran, N Cohen, F Havet, T Mülle. Acyclic edge-coloring of planar graphs. SIAM J Discrete Math 2011; 25(2): 463–478
3	P M S Fialho, B N B de Lima, A Procacci. A new bound on the acyclic edge chromatic number. Discrete Math 2020; 343(11): 112037
4	J Fiamčík. The acyclic chromatic class of a graph. Math. Slovaca 1978; 28(2): 139–145
5	J F Hou, G Z Liu, J L Wu. Acyclic edge coloring of planar graphs without small cycles. Graphs Combin 2012; 28(2): 215–226
6	J F Hou, W T Wang, X R Zhang. Acyclic edge coloring of planar graphs with girth at least 5. Discrete Appl Math 2013; 161(18): 2958–2967
7	D Hudák, F Kardoš, B Lužar, R Soták, R Škrekovski. Acyclic edge coloring of planar graphs with ∆ colors. Discrete Appl Math 2012; 160(9): 1356–1368
8	L KirousisJ Livieratos. The acyclic chromatic index is less than the double of the max degree. 2022, arXiv: 1901.07856v7
9	M MolloyB Reed. Further algorithmic aspects of the local lemma, In: STOC ’98 (Dallas, TX). New York: ACM, 1999, 524−529
10	Q J Shu, Y Chen, S G Han, G H Lin, E Miyano, A Zhang. Acyclic edge coloring conjecture is true on planar graphs without intersecting triangles. Theoret Comput Sci 2021; 882: 77–108
11	Q J Shu, W F Wang, Y Q Wang. Acyclic edge coloring of planar graphs without 5-cycles. Discrete Appl Math 2012; 160(7/8): 1211–1223
12	Q J Shu, W F Wang, Y Q Wang. Acyclic chromatic indices of planar graphs with girth at least 4. J Graph Theory 2013; 73(4): 386–399
13	T Wang, Y Q Zhang. Further result on acyclic chromatic index of planar graphs. Discrete Appl Math 2016; 201: 228–247
14	W F Wang, Q J Shu, K Wang, P Wang. Acyclic chromatic indices of planar graphs with large girth. Discrete Appl Math 2011; 159(12): 1239–1253
15	W F Wang, Q J Shu, Y Q Wang. A new upper bound on the acyclic chromatic indices of planar graphs. European J Combin 2013; 34(2): 338–354
16	W F Wang, Q J Shu, Y Q Wang. Acyclic edge coloring of planar graphs without 4-cycles. J Comb Optim 2013; 25(4): 562–586
17	Y Q Wang, Q J Shu. Acyclic edge coloring of planar graphs. J Jiangsu Norm Univ (Nat Sci Ed) 2014; 32(3): 22–26
18	Y Q Wang, Q J Shu, W F Wang. 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	Y Q Wang, Q J Shu, J L Wu, W W Zhang. Acyclic edge coloring of planar graphs without a 3-cycle adjacent to a 6-cycle. J Comb Optim 2014; 28(3): 692–715
20	Y Q Wang, P Sheng. Improved upper bound for acyclic chromatic index of planar graphs without 4-cycles. J Comb Optim 2014; 27(3): 519–529
21	D Z Xie, Y Q Wu. Acyclic edge coloring of planar graphs without adjacent triangles. J Math Res Appl 2012; 32(4): 407–414

[1]	Jufeng ZHANG, Min CHEN, Yiqiao WANG. *(3, 1)^-choosability of plane graphs without adjacent single cycles**[J]. Front. Math. China, 2024, 19(2): 101-115.
[2]	Linlin FU, Jiahao XU, Fan WU. New proof of continuity of Lyapunov exponents for a class of smooth Schrödinger cocycles with weak Liouville frequencies[J]. Front. Math. China, 2020, 15(3): 467-489.
[3]	Xie-Bin CHEN. Matchings extend to Hamiltonian cycles in hypercubes with faulty edges[J]. Front. Math. China, 2019, 14(6): 1117-1132.
[4]	Lei LIU. Lagrangian Grassmann manifold Λ(2)[J]. Front. Math. China, 2018, 13(2): 341-365.
[5]	Ruipu BAI,Ying LI. Extensions of n-Hom Lie algebras[J]. Front. Math. China, 2015, 10(3): 511-522.
[6]	Min ZHOU,Haitao CAO. Almost resolvable maximum packings of complete graphs with 5-cycles[J]. Front. Math. China, 2015, 10(2): 461-475.
[7]	Xie-Bin CHEN. Fault-free Hamiltonian cycles passing through a prescribed linear forest in 3-ary n-cube with faulty edges[J]. Front Math Chin, 2014, 9(1): 17-30.
[8]	Hao FAN, Guizhen LIU. Properties of Hamilton cycles of circuit graphs of matroids[J]. Front Math Chin, 2013, 8(4): 801-809.
[9]	Yanhong BAO, Xianneng DU, Yu YE. Poisson structures on basic cycles[J]. Front Math Chin, 2012, 7(3): 385-396.
[10]	Kai TAO. Continuity of Lyapunov exponent for analytic quasi-periodic cocycles on higher-dimensional torus[J]. Front Math Chin, 2012, 7(3): 521-542.
[11]	Linping PENG. Quadratic perturbations of a quadratic reversible center of genus one[J]. Front Math Chin, 2011, 6(5): 911-930.
[12]	Han REN, Ni CAO, . Finding short cycles in embedded graph in polynomial time[J]. Front. Math. China, 2010, 5(2): 319-327.
[13]	Huanxia FA, Xiaoyan ZHENG, Junbo LI, . Second Leibniz cohomology group of twisted N = 2 superconformal algebra[J]. Front. Math. China, 2009, 4(4): 627-635.
[14]	Xuanji HOU, . Stable one-dimensional quasi-periodic cocycles on unitary group[J]. Front. Math. China, 2009, 4(4): 651-658.
[15]	Jun-Ming XU, Meijie MA. Survey on path and cycle embedding in some networks[J]. Front Math Chin, 2009, 4(2): 217-252.

Viewed

Full text

Abstract

Cited

Shared

Discussed