Geodesic
Acyclic 4-choosability of planar graphs without 4-cycles
Czechoslovak Mathematical Journal, Tome 70 (2020) no. 1, pp. 161-178 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.21136/CMJ.2019.0197-18
Classification : 05C10, 05C15
Keywords: planar graph; acyclic coloring; choosability; intersecting cycle 
@article{10_21136_CMJ_2019_0197_18,
     author = {Sun, Yingcai and Chen, Min},
     title = {Acyclic 4-choosability of planar graphs without 4-cycles},
     journal = {Czechoslovak Mathematical Journal},
     pages = {161--178},
     year = {2020},
     volume = {70},
     number = {1},
     doi = {10.21136/CMJ.2019.0197-18},
     mrnumber = {4078351},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2019.0197-18/}
}
TY  - JOUR
AU  - Sun, Yingcai
AU  - Chen, Min
TI  - Acyclic 4-choosability of planar graphs without 4-cycles
JO  - Czechoslovak Mathematical Journal
PY  - 2020
SP  - 161
EP  - 178
VL  - 70
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2019.0197-18/
DO  - 10.21136/CMJ.2019.0197-18
LA  - en
ID  - 10_21136_CMJ_2019_0197_18
ER  - 
%0 Journal Article
%A Sun, Yingcai
%A Chen, Min
%T Acyclic 4-choosability of planar graphs without 4-cycles
%J Czechoslovak Mathematical Journal
%D 2020
%P 161-178
%V 70
%N 1
%U http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2019.0197-18/
%R 10.21136/CMJ.2019.0197-18
%G en
%F 10_21136_CMJ_2019_0197_18
Sun, Yingcai; Chen, Min. Acyclic 4-choosability of planar graphs without 4-cycles. Czechoslovak Mathematical Journal, Tome 70 (2020) no. 1, pp. 161-178. doi: 10.21136/CMJ.2019.0197-18

[1] Albertson, M. O., Berman, D. M.: Every planar graph has an acyclic 7-coloring. Isr. J. Math. 28 (1977), 169-174. | DOI | MR | JFM

[2] Borodin, O. V.: On acyclic colorings of planar graphs. Discrete Math. 306 (2006), 953-972. | DOI | MR | JFM

[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 | MR | JFM

[4] Borodin, O. V., Ivanova, A. O.: Acyclic 5-choosability of planar graphs without 4-cycles. Sib. Math. J. 52 (2011), 411-425. | DOI | MR | JFM

[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 | MR | JFM

[6] Chen, M., Raspaud, A.: On acyclic 4-choosability of planar graphs without short cycles. Discrete Math. 310 (2010), 2113-2118. | DOI | MR | JFM

[7] Chen, M., Raspaud, A.: A sufficient condition for planar graphs to be acyclically 5-choosable. J. Graph Theory 70 (2012), 135-151. | DOI | MR | JFM

[8] Chen, M., Raspaud, A.: Planar graphs without 4- and 5-cycles are acyclically 4-choosable. Discrete Appl. Math. 161 (2013), 921-931. | DOI | MR | JFM

[9] Chen, M., Raspaud, A., Roussel, N., Zhu, X.: Acyclic 4-choosability of planar graphs. Discrete Math. 311 (2011), 92-101. | DOI | MR | JFM

[10] Chen, M., Wang, W.: Acyclic 5-choosability of planar graphs without 4-cycles. Discrete Math. 308 (2008), 6216-6225. | DOI | MR | JFM

[11] Grünbaum, B.: Acyclic colorings of planar graphs. Isr. J. Math. 14 (1973), 390-408. | DOI | MR | JFM

[12] Kostočka, A. V.: Acyclic 6-coloring of planar graphs. Metody Diskretn. Anal. Russian 28 (1976), 40-54. | MR | JFM

[13] Mitchem, J.: Every planar graph has an acyclic 8-coloring. Duke Math. J. 41 (1974), 177-181. | DOI | MR | JFM

[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 | MR | JFM

[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 | MR | JFM

[16] Montassier, M., Raspaud, A., Wang, W.: Acyclic 5-choosability of planar graphs without small cycles. J. Graph Theory 54 (2007), 245-260. | DOI | MR | JFM

[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 | MR | JFM

[18] Wang, W., Chen, M.: Planar graphs without 4-cycles are acyclically 6-choosable. J. Graph Theory 61 (2009), 307-323. | DOI | MR | JFM

[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 | MR | JFM

[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 | MR | JFM

Cité par Sources :