Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
planar graph; acyclic coloring; choosability; intersecting cycle
planar graph; acyclic coloring; choosability; intersecting cycle
Summary:
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.
References:
[1] Albertson, M. O., Berman, D. M.: 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] Borodin, O. V.: 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] Borodin, O. V., Flaass, D. G. Fon-Der, Kostochka, A. V., Raspaud, A., Sopena, E.: 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] Borodin, O. V., Ivanova, A. O.: 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] Borodin, O. V., Ivanova, A. O., Raspaud, A.: 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] Chen, M., Raspaud, A.: 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] Chen, M., Raspaud, A.: 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] Chen, M., Raspaud, A.: 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] Chen, M., Raspaud, A., Roussel, N., Zhu, X.: 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] Chen, M., Wang, W.: 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] Grünbaum, B.: Acyclic colorings of planar graphs. Isr. J. Math. 14 (1973), 390-408. DOI 10.1007/BF02764716 | MR 0317982 | Zbl 0265.05103
[12] Kostočka, A. V.: Acyclic 6-coloring of planar graphs. Metody Diskretn. Anal. Russian 28 (1976), 40-54. MR 0498210 | Zbl 0412.05043
[13] Mitchem, J.: 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] Montassier, M.: Acyclic 4-choosability of planar graphs with girth at least 5. Graph Theory in Paris A. Bondy, et al. Trends in Mathematics, Birkhäuser, Basel (2007), 299-310. DOI 10.1007/978-3-7643-7400-6_23 | MR 2279184 | Zbl 1118.05036
[15] Montassier, M., Raspaud, A., Wang, W.: Acyclic 4-choosability of planar graphs without cycles of specific lengths. Topics in Discrete Mathematics M. Klazar, et al. Algorithms and Combinatorics 26 Springer, Berlin (2006), 473-491. DOI 10.1007/3-540-33700-8_23 | MR 2249282 | Zbl 1120.05034
[16] Montassier, M., Raspaud, A., Wang, W.: 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] Sun, Y., Chen, M., Chen, D.: 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] Wang, W., Chen, M.: 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] Wang, W., Zhang, G., Chen, M.: 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] Zhang, H., Xu, B.: 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
Search
Partner of
