Czechoslovak Mathematical Journal, first online, pp. 1-18


Acyclic 4-choosability of planar graphs without 4-cycles

Yingcai Sun, Min Chen

Received April 9, 2019.   Published online September 16, 2019.

Abstract:  A proper vertex coloring of a graph $G$ is acyclic if there is no bicolored cycle in $G$. In other words, each cycle of $G$ must be colored with at least three colors. Given a list assignment $L=\{L(v)\colon v\in V\}$, if there exists an acyclic coloring $\pi$ of $G$ such that $\pi(v)\in L(v)$ for all $v\in V$, then we say that $G$ is acyclically $L$-colorable. If $G$ is acyclically $L$-colorable for any list assignment $L$ with $|L(v)|\ge k$ for all $v\in V$, then $G$ is acyclically $k$-choosable. In 2006, Montassier, Raspaud and Wang conjectured that every planar graph without 4-cycles is acyclically 4-choosable. However, this has been as yet verified only for some restricted classes of planar graphs. In this paper, we prove that every planar graph with neither 4-cycles nor intersecting $i$-cycles for each $i\in\{3,5\}$ is acyclically 4-choosable.
Keywords:  planar graph; acyclic coloring; choosability; intersecting cycle
Classification MSC:  05C10; 05C15
DOI:  10.21136/CMJ.2019.0197-18

PDF available at:  Springer   Institute of Mathematics CAS

References:
[1] M. O. Albertson, D. M. Berman: Every planar graph has an acyclic 7-coloring. Isr. J. Math. 28 (1977), 169-174. DOI 10.1007/BF02759792 | MR 0463006 | Zbl 0374.05022
[2] O. V. Borodin: On acyclic colorings of planar graphs. Discrete Math. 306 (2006), 953-972. DOI 10.1016/j.disc.2006.03.017 | MR 0534939 | Zbl 1093.05022
[3] O. V. Borodin, D. G. Fon-Der Flaass, A. V. Kostochka, A. Raspaud, E. Sopena: Acyclic list 7-coloring of planar graphs. J. Graph Theory 40 (2002), 83-90. DOI 10.1002/jgt.10035 | MR 1899114 | Zbl 1004.05029
[4] O. V. Borodin, A. O. Ivanova: Acyclic 5-choosability of planar graphs without 4-cycles. Sib. Math. J. 52 (2011), 411-425. DOI 10.1134/S0037446611030049 | MR 2858640 | Zbl 1294.05057
[5] O. V. Borodin, A. O. Ivanova, A. Raspaud: Acyclic 4-choosability of planar graphs with neither 4-cycles nor triangular 6-cycles. Discrete Math. 310 (2010), 2946-2950. DOI 10.1016/j.disc.2010.07.001 | MR 2677655 | Zbl 1209.05063
[6] M. Chen, A. Raspaud: On acyclic 4-choosability of planar graphs without short cycles. Discrete Math. 310 (2010), 2113-2118. DOI 10.1016/j.disc.2010.03.036 | MR 2651808 | Zbl 1221.05075
[7] M. Chen, A. Raspaud: A sufficient condition for planar graphs to be acyclically 5-choosable. J. Graph Theory 70 (2012), 135-151. DOI 10.1002/jgt.20604 | MR 2920995 | Zbl 1242.05089
[8] M. Chen, A. Raspaud: Planar graphs without 4- and 5-cycles are acyclically 4-choosable. Discrete Appl. Math. 161 (2013), 921-931. DOI 10.1016/j.dam.2012.11.006 | MR 3030578 | Zbl 1262.05029
[9] M. Chen, A. Raspaud, N. Roussel, X. Zhu: Acyclic 4-choosability of planar graphs. Discrete Math. 311 (2011), 92-101. DOI 10.1016/j.disc.2010.10.003 | MR 2737973 | Zbl 1216.05028
[10] M. Chen, W. Wang: Acyclic 5-choosability of planar graphs without 4-cycles. Discrete Math. 308 (2008), 6216-6225. DOI 10.1016/j.disc.2007.11.076 | MR 2464910 | Zbl 1189.05059
[11] B. Grünbaum: Acyclic colorings of planar graphs. Isr. J. Math. 14 (1973), 390-408. DOI 10.1007/BF02764716 | MR 0317982 | Zbl 0265.05103
[12] A. V. Kostočka: Acyclic 6-coloring of planar graphs. Metody Diskretn. Anal. 28 (1976), 40-54. (In Russian.) MR 0498210 | Zbl 0412.05043
[13] J. Mitchem: Every planar graph has an acyclic 8-coloring. Duke Math. J. 41 (1974), 177-181. DOI 10.1215/S0012-7094-74-04119-2 | MR 0371709 | Zbl 0284.05103
[14] M. Montassier: Acyclic 4-choosability of planar graphs with girth at least 5. Graph Theory in Paris (A. Bondy, et al., eds.). Trends in Mathematics, Birkhäuser, Basel (2007), 299-310. DOI 10.1007/978-3-7643-7400-6_23 | MR 2279184 | Zbl 1118.05036
[15] M. Montassier, A. Raspaud, W. Wang: Acyclic 4-choosability of planar graphs without cycles of specific lengths. Topics in Discrete Mathematics (M. Klazar, et al., eds.). Algorithms and Combinatorics 26 Springer, Berlin (2006), 473-491. DOI 10.1007/3-540-33700-8_23 | MR 2249282 | Zbl 1120.05034
[16] M. Montassier, A. Raspaud, W. Wang: Acyclic 5-choosability of planar graphs without small cycles. J. Graph Theory 54 (2007), 245-260. DOI 10.1002/jgt.20206 | MR 2290230 | Zbl 1114.05037
[17] Y. Sun, M. Chen, D. Chen: Acyclic 4-choosability of planar graphs without intersecting short cycles. Discrete Math. Algorithms Appl. 10 (2018), Article ID 1850014, 11 pages. DOI 10.1142/S1793830918500143 | MR 3763491 | Zbl 1380.05081
[18] W. Wang, M. Chen: Planar graphs without 4-cycles are acyclically 6-choosable. J. Graph Theory 61 (2009), 307-323. DOI 10.1002/jgt.20381 | MR 2536885 | Zbl 1185.05068
[19] W. Wang, G. Zhang, M. Chen: Acyclic 6-choosability of planar graphs without adjacent short cycles. Sci. China, Math. 57 (2014), 197-209. DOI 10.1007/s11425-013-4572-6 | MR 3146526 | Zbl 1299.05137
[20] H. Zhang, B. Xu: Acyclic 5-choosability of planar graphs with neither 4-cycles nor chordal 6-cycles. Discrete Math. 309 (2009), 6087-6091. DOI 10.1016/j.disc.2009.05.018 | MR 2552644 | Zbl 1204.05049

Affiliations:   Yingcai Sun, Min Chen (corresponding author), Department of Mathematics, Zhejiang Normal University, 688 Yingbin Avenue, Jinhua 321004, P. R. China, e-mail: chenmin@zjnu.cn


 
PDF available at: