| Title:
|
Acyclic 4-choosability of planar graphs without 4-cycles (English) |
| Author:
|
Sun, Yingcai |
| Author:
|
Chen, Min |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
70 |
| Issue:
|
1 |
| Year:
|
2020 |
| Pages:
|
161-178 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
planar graph |
| Keyword:
|
acyclic coloring |
| Keyword:
|
choosability |
| Keyword:
|
intersecting cycle |
| MSC:
|
05C10 |
| MSC:
|
05C15 |
| idZBL:
|
07217126 |
| idMR:
|
MR4078351 |
| DOI:
|
10.21136/CMJ.2019.0197-18 |
| . |
| Date available:
|
2020-03-10T10:16:31Z |
| Last updated:
|
2022-04-04 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/148047 |
| . |
| Reference:
|
[1] Albertson, M. O., Berman, D. M.: Every planar graph has an acyclic 7-coloring.Isr. J. Math. 28 (1977), 169-174. Zbl 0374.05022, MR 0463006, 10.1007/BF02759792 |
| Reference:
|
[2] Borodin, O. V.: On acyclic colorings of planar graphs.Discrete Math. 306 (2006), 953-972. Zbl 1093.05022, MR 0534939, 10.1016/j.disc.2006.03.017 |
| Reference:
|
[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. Zbl 1004.05029, MR 1899114, 10.1002/jgt.10035 |
| Reference:
|
[4] Borodin, O. V., Ivanova, A. O.: Acyclic 5-choosability of planar graphs without 4-cycles.Sib. Math. J. 52 (2011), 411-425. Zbl 1294.05057, MR 2858640, 10.1134/S0037446611030049 |
| Reference:
|
[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. Zbl 1209.05063, MR 2677655, 10.1016/j.disc.2010.07.001 |
| Reference:
|
[6] Chen, M., Raspaud, A.: On acyclic 4-choosability of planar graphs without short cycles.Discrete Math. 310 (2010), 2113-2118. Zbl 1221.05075, MR 2651808, 10.1016/j.disc.2010.03.036 |
| Reference:
|
[7] Chen, M., Raspaud, A.: A sufficient condition for planar graphs to be acyclically 5-choosable.J. Graph Theory 70 (2012), 135-151. Zbl 1242.05089, MR 2920995, 10.1002/jgt.20604 |
| Reference:
|
[8] Chen, M., Raspaud, A.: Planar graphs without 4- and 5-cycles are acyclically 4-choosable.Discrete Appl. Math. 161 (2013), 921-931. Zbl 1262.05029, MR 3030578, 10.1016/j.dam.2012.11.006 |
| Reference:
|
[9] Chen, M., Raspaud, A., Roussel, N., Zhu, X.: Acyclic 4-choosability of planar graphs.Discrete Math. 311 (2011), 92-101. Zbl 1216.05028, MR 2737973, 10.1016/j.disc.2010.10.003 |
| Reference:
|
[10] Chen, M., Wang, W.: Acyclic 5-choosability of planar graphs without 4-cycles.Discrete Math. 308 (2008), 6216-6225. Zbl 1189.05059, MR 2464910, 10.1016/j.disc.2007.11.076 |
| Reference:
|
[11] Grünbaum, B.: Acyclic colorings of planar graphs.Isr. J. Math. 14 (1973), 390-408. Zbl 0265.05103, MR 0317982, 10.1007/BF02764716 |
| Reference:
|
[12] Kostočka, A. V.: Acyclic 6-coloring of planar graphs.Metody Diskretn. Anal. Russian 28 (1976), 40-54. Zbl 0412.05043, MR 0498210 |
| Reference:
|
[13] Mitchem, J.: Every planar graph has an acyclic 8-coloring.Duke Math. J. 41 (1974), 177-181. Zbl 0284.05103, MR 0371709, 10.1215/S0012-7094-74-04119-2 |
| Reference:
|
[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. Zbl 1118.05036, MR 2279184, 10.1007/978-3-7643-7400-6_23 |
| Reference:
|
[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. Zbl 1120.05034, MR 2249282, 10.1007/3-540-33700-8_23 |
| Reference:
|
[16] Montassier, M., Raspaud, A., Wang, W.: Acyclic 5-choosability of planar graphs without small cycles.J. Graph Theory 54 (2007), 245-260. Zbl 1114.05037, MR 2290230, 10.1002/jgt.20206 |
| Reference:
|
[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. Zbl 1380.05081, MR 3763491, 10.1142/S1793830918500143 |
| Reference:
|
[18] Wang, W., Chen, M.: Planar graphs without 4-cycles are acyclically 6-choosable.J. Graph Theory 61 (2009), 307-323. Zbl 1185.05068, MR 2536885, 10.1002/jgt.20381 |
| Reference:
|
[19] Wang, W., Zhang, G., Chen, M.: Acyclic 6-choosability of planar graphs without adjacent short cycles.Sci. China, Math. 57 (2014), 197-209. Zbl 1299.05137, MR 3146526, 10.1007/s11425-013-4572-6 |
| Reference:
|
[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. Zbl 1204.05049, MR 2552644, 10.1016/j.disc.2009.05.018 |
| . |
