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 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 ) : v ∈ V } , if there exists an acyclic coloring π of G such that π ( v ) ∈ L ( v ) for all v ∈ V , then we say that G is acyclically L -colorable. If G is acyclically L -colorable for any list assignment L with | L ( v ) | ≥ k for all v ∈ 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 ∈ { 3 , 5 } 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.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.