Acyclic 4-choosability of planar graphs without 4-cycles

Yingcai Sun; Min Chen

Czechoslovak Mathematical Journal (2020)

  • Volume: 70, Issue: 1, page 161-178
  • ISSN: 0011-4642

Abstract

top
A proper vertex coloring of a graph is acyclic if there is no bicolored cycle in . In other words, each cycle of must be colored with at least three colors. Given a list assignment , if there exists an acyclic coloring of such that for all , then we say that is acyclically -colorable. If is acyclically -colorable for any list assignment with for all , then is acyclically -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 -cycles for each is acyclically 4-choosable.

How to cite

top

Sun, Yingcai, and Chen, Min. "Acyclic 4-choosability of planar graphs without 4-cycles." Czechoslovak Mathematical Journal 70.1 (2020): 161-178. <http://eudml.org/doc/297337>.

@article{Sun2020,
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=\lbrace L(v)\colon v\in V\rbrace $, 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 \lbrace 3,5\rbrace $ is acyclically 4-choosable.},
author = {Sun, Yingcai, Chen, Min},
journal = {Czechoslovak Mathematical Journal},
keywords = {planar graph; acyclic coloring; choosability; intersecting cycle},
language = {eng},
number = {1},
pages = {161-178},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Acyclic 4-choosability of planar graphs without 4-cycles},
url = {http://eudml.org/doc/297337},
volume = {70},
year = {2020},
}

TY - JOUR
AU - Sun, Yingcai
AU - Chen, Min
TI - Acyclic 4-choosability of planar graphs without 4-cycles
JO - Czechoslovak Mathematical Journal
PY - 2020
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 70
IS - 1
SP - 161
EP - 178
AB - 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=\lbrace L(v)\colon v\in V\rbrace $, 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 \lbrace 3,5\rbrace $ is acyclically 4-choosable.
LA - eng
KW - planar graph; acyclic coloring; choosability; intersecting cycle
UR - http://eudml.org/doc/297337
ER -

References

top
  1. Albertson, M. O., Berman, D. M., 10.1007/BF02759792, Isr. J. Math. 28 (1977), 169-174. (1977) Zbl0374.05022MR0463006DOI10.1007/BF02759792
  2. Borodin, O. V., 10.1016/j.disc.2006.03.017, Discrete Math. 306 (2006), 953-972. (2006) Zbl1093.05022MR0534939DOI10.1016/j.disc.2006.03.017
  3. Borodin, O. V., Flaass, D. G. Fon-Der, Kostochka, A. V., Raspaud, A., Sopena, E., 10.1002/jgt.10035, J. Graph Theory 40 (2002), 83-90. (2002) Zbl1004.05029MR1899114DOI10.1002/jgt.10035
  4. Borodin, O. V., Ivanova, A. O., 10.1134/S0037446611030049, Sib. Math. J. 52 (2011), 411-425. (2011) Zbl1294.05057MR2858640DOI10.1134/S0037446611030049
  5. Borodin, O. V., Ivanova, A. O., Raspaud, A., 10.1016/j.disc.2010.07.001, Discrete Math. 310 (2010), 2946-2950. (2010) Zbl1209.05063MR2677655DOI10.1016/j.disc.2010.07.001
  6. Chen, M., Raspaud, A., 10.1016/j.disc.2010.03.036, Discrete Math. 310 (2010), 2113-2118. (2010) Zbl1221.05075MR2651808DOI10.1016/j.disc.2010.03.036
  7. Chen, M., Raspaud, A., 10.1002/jgt.20604, J. Graph Theory 70 (2012), 135-151. (2012) Zbl1242.05089MR2920995DOI10.1002/jgt.20604
  8. Chen, M., Raspaud, A., 10.1016/j.dam.2012.11.006, Discrete Appl. Math. 161 (2013), 921-931. (2013) Zbl1262.05029MR3030578DOI10.1016/j.dam.2012.11.006
  9. Chen, M., Raspaud, A., Roussel, N., Zhu, X., 10.1016/j.disc.2010.10.003, Discrete Math. 311 (2011), 92-101. (2011) Zbl1216.05028MR2737973DOI10.1016/j.disc.2010.10.003
  10. Chen, M., Wang, W., 10.1016/j.disc.2007.11.076, Discrete Math. 308 (2008), 6216-6225. (2008) Zbl1189.05059MR2464910DOI10.1016/j.disc.2007.11.076
  11. Grünbaum, B., 10.1007/BF02764716, Isr. J. Math. 14 (1973), 390-408. (1973) Zbl0265.05103MR0317982DOI10.1007/BF02764716
  12. Kostočka, A. V., Acyclic 6-coloring of planar graphs, Metody Diskretn. Anal. Russian 28 (1976), 40-54. (1976) Zbl0412.05043MR0498210
  13. Mitchem, J., 10.1215/S0012-7094-74-04119-2, Duke Math. J. 41 (1974), 177-181. (1974) Zbl0284.05103MR0371709DOI10.1215/S0012-7094-74-04119-2
  14. Montassier, M., 10.1007/978-3-7643-7400-6_23, Graph Theory in Paris A. Bondy, et al. Trends in Mathematics, Birkhäuser, Basel (2007), 299-310. (2007) Zbl1118.05036MR2279184DOI10.1007/978-3-7643-7400-6_23
  15. Montassier, M., Raspaud, A., Wang, W., 10.1007/3-540-33700-8_23, Topics in Discrete Mathematics M. Klazar, et al. Algorithms and Combinatorics 26 Springer, Berlin (2006), 473-491. (2006) Zbl1120.05034MR2249282DOI10.1007/3-540-33700-8_23
  16. Montassier, M., Raspaud, A., Wang, W., 10.1002/jgt.20206, J. Graph Theory 54 (2007), 245-260. (2007) Zbl1114.05037MR2290230DOI10.1002/jgt.20206
  17. Sun, Y., Chen, M., Chen, D., 10.1142/S1793830918500143, Discrete Math. Algorithms Appl. 10 (2018), Article ID 1850014, 11 pages. (2018) Zbl1380.05081MR3763491DOI10.1142/S1793830918500143
  18. Wang, W., Chen, M., 10.1002/jgt.20381, J. Graph Theory 61 (2009), 307-323. (2009) Zbl1185.05068MR2536885DOI10.1002/jgt.20381
  19. Wang, W., Zhang, G., Chen, M., 10.1007/s11425-013-4572-6, Sci. China, Math. 57 (2014), 197-209. (2014) Zbl1299.05137MR3146526DOI10.1007/s11425-013-4572-6
  20. Zhang, H., Xu, B., 10.1016/j.disc.2009.05.018, Discrete Math. 309 (2009), 6087-6091. (2009) Zbl1204.05049MR2552644DOI10.1016/j.disc.2009.05.018

NotesEmbed ?

top

You must be logged in to post comments.