A sufficient condition for acyclic 5-choosability of planar graphs without 5-cycles
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
A proper vertex coloring of a graph $G$ is acyclic if $G$ contains no bicolored cycle. A graph $G$ is acyclically $L$-list colorable if for a given list assignment $L=\{L(v): v\in V(G)\}$, there exists an acyclic coloring $\phi$ of $G$ such that $\phi(v)\in L(v)$ for all $v\in V(G)$. A graph $G$ is acyclically $k$-choosable if $G$ is acyclically $L$-list colorable for any list assignment with $L(v)\geq k$ for all $v\in V(G)$. Let $G$ be a planar graph without $5$-cycles and adjacent $4$-cycles. In this article, we prove that $G$ is acyclically $5$-choosable if every vertex $v$ in $G$ is incident with at most one $i$-cycle, $i\in\{6,7\}$.
Abstract
A proper vertex coloring of a graph $G$ is acyclic if $G$ contains no bicolored cycle. A graph $G$ is acyclically $L$-list colorable if for a given list assignment $L=\{L(v): v\in V(G)\}$, there exists an acyclic coloring $\phi$ of $G$ such that $\phi(v)\in L(v)$ for all $v\in V(G)$. A graph $G$ is acyclically $k$-choosable if $G$ is acyclically $L$-list colorable for any list assignment with $L(v)\geq k$ for all $v\in V(G)$. Let $G$ be a planar graph without $5$-cycles and adjacent $4$-cycles. In this article, we prove that $G$ is acyclically $5$-choosable if every vertex $v$ in $G$ is incident with at most one $i$-cycle, $i\in\{6,7\}$.
참고문헌 (18)
- J. A. Bondy, "Graph Theory with Applications" (1976), MacMillan
- O. V. Borodin, "Acyclic list 7-coloring of planar graphs", J. Graph Theory, 40(2), pp.83~90 (2002)[DOI]
- O. V. Borodin, "Acyclic 5-choosability of planar graphs without 4-cycles", Siberian Math. J., 52(3), pp.411~425 (2011)[DOI]
- O. V. Borodin, "Acyclic 5-choosability of planar graphs without adjacent short cycles", J. Graph Theory, 68(2), pp.169~176 (2011)[DOI]
- O. V. Borodin, "Acyclic 4-choosability of planar graphs without adjacent short cycles", Discrete Math., 312(22), pp.3335~3341 (2012)[DOI]
- O. V. Borodin, "Acyclic 4-choosability of planar graphs with no 4- and 5-cycles", J. Graph Theory, 72(4), pp.374~397 (2013)[DOI]
- O. V. Borodin, "Acyclic 4-choosability of planar graphs with neither 4-cycles nor triangular 6-cycles", Discrete Math., 310(21), pp.2946~2950 (2010)[DOI]
- M. Chen, "A sufficient condition for planar graphs to be acyclically 5-choosable", J. Graph Theory, 70(2), pp.135~151 (2012)[DOI]
- M. Chen, "Planar graphs without 4- and 5-cycles are acyclically 4-choosable", Discrete Appl. Math., 161(7-8), pp.921~931 (2013)[DOI]
- M. Chen, "Acyclic 4-choosability of planar graphs", Discrete Math., 311(1), pp.92~101 (2011)[DOI]
- M. Chen, "Acyclic 5-choosability of planar graphs without 4-cycles", Discrete Math., 308(24), pp.6216~6225 (2008)[DOI]
- B. Grunbaum, "Acyclic colorings of planar graphs", Israel J. Math., 14(3), pp.390~408 (1973)[DOI]
- J. F. Hou, "Every toroidal graph is acyclically 8-choosable", Acta Math. Sin. (Engl. Ser.), 30(2), pp.343~352 (2014)[DOI]
- M. Montassier, "Acyclic 4-choosability of Planar Graphs with Girth at Least 5, Graph theory in Paris", pp.299~310 (2007)
- M. Montassier, "On the acyclic choosability of graphs", J. Graph Theory, 51(4), pp.281~300 (2006)[DOI]
- M. Montassier, "Acyclic 5-choosability of planar graphs without small cycles", J. Graph Theory, 54(3), pp.245~260 (2007)[DOI]
- W. F. Wang, "Planar graphs without 4-cycles are 6-choosable", J. Graph Theory, 61(4), pp.307~323 (2009)[DOI]
- W. F. Wang, "Acyclic 6-choosability of planar graphs without adjacent short cycles", Sci. China Math., 57(1), pp.197~209 (2014)[DOI]