TY - JOUR
ID - 881
TI - On list vertex 2-arboricity of toroidal graphs without cycles of specific length
JO - Bulletin of the Iranian Mathematical Society
JA - BIMS
LA - en
SN - 1017-060X
AU - Zhang, H.
AD - School of Mathematical Science, Huaiyin Normal University, 111 Changjiang West Road, Huaian, Jiangsu, 223300, P. R. China.
Y1 - 2016
PY - 2016
VL - 42
IS - 5
SP - 1293
EP - 1303
KW - Vertex arboricity
KW - toroidal graph
KW - structure
KW - cycle
DO -
N2 - The vertex arboricity $\rho(G)$ of a graph $G$ is the minimum number of subsets into which the vertex set $V(G)$ can be partitioned so that each subset induces an acyclic graph. A graph $G$ is called list vertex $k$-arborable if for any set $L(v)$ of cardinality at least $k$ at each vertex $v$ of $G$, one can choose a color for each $v$ from its list $L(v)$ so that the subgraph induced by every color class is a forest. The smallest $k$ for a graph to be list vertex $k$-arborable is denoted by $\rho_l(G)$. Borodin, Kostochka and Toft (Discrete Math. 214 (2000) 101-112) first introduced the list vertex arboricity of $G$. In this paper, we prove that $\rho_l(G)\leq 2$ for any toroidal graph without 5-cycles. We also show that $\rho_l(G)\leq 2$ if $G$ contains neither adjacent 3-cycles nor cycles of lengths 6 and 7.
UR - http://bims.iranjournals.ir/article_881.html
L1 - http://bims.iranjournals.ir/article_881_1c2751a2e851f892b91c1fd5de3e21f4.pdf
ER -