Geodesic
Acyclic 4-choosability of planar graphs without 4-cycles
Czechoslovak Mathematical Journal, Tome 70 (2020) no. 1, pp. 161-178

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

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},
     publisher = {mathdoc},
     volume = {70},
     number = {1},
     year = {2020},
     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
PB  - mathdoc
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
%I mathdoc
%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

Cité par Sources :