On list vertex 2-arboricity of toroidal graphs without cycles of specific length

Document Type : Research Paper

Author

School of Mathematical Science‎, ‎Huaiyin Normal University‎, 111 Changjiang West Road‎, ‎Huaian‎, ‎Jiangsu‎, 223300‎, ‎P‎. ‎R‎. ‎China.

Abstract

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.

Keywords

Main Subjects

References

Y. Alavi, D. Green, J. Liu and J. Wang, On linear vertex-arboricity of graphs, Congres. Numer. 82 (1991) 187--192.
Y. Alavi, J. Liu and J. Wang, On linear vertex-arboricity of complementary graphs, J. Graph Theory 18 (1994), no. 3, 315--322.
O. V. Borodin and A. O. Ivanova, Planar graphs without 4-cycles adjacent to 3-cycles are list vertex 2-arborable, J. Graph Theory 62 (2009), no. 3, 234--240.
O. V. Borodin and A. O. Ivanova, List 2-arboricity of planar graphs with no triangles at distance less than two, Sib. Elektron. Mat. Izv. (http://semr.math.nsc.ru) 5 (2008) 211--214.
O. V. Borodin, A. V. Kostochka and B. Toft, Variable degeneracy: extension of Brook's and Gallai's theorems, Discrete Math. 214 (2000), no. 1-3, 101--112.
S. A. Burr, An inequality involving the vertex arboricity and edge arboricity of a graph, J. Graph Theory 10 (1986), no. 3, 403--404.
 L. Cai, W. Wang and X. Zhu, Choosability of toroidal graphs without short cycles, J. Graph Theory 65 (2010), no. 1, 1--15.
 G. J. Chang, C. Chen and Y. Chen, Vertex and tree arboricities of graphs, J. Comb. Optim. 8 (2004), no. 3, 295--306.
G. Chartrand and H. V. Kronk, The point-arboricity of planar graphs, J. Lond. Math. Soc. 44 (1969) 612--616.
G. Chartrand, H. V. Kronk and C. E. Wall, The point-arboricity of a graph, Israel J. Math. 6 (1968) 169--175.
Z. Chen and X. He, Parallel complexity of partitioning a planar graph into vertexinduced forests, Discrete Appl. Math. 69 (1996), no. 1-2, 183--198.
 M. Chen, A. Raspaud and W. Wang, Vertex-arboricity of planar graphs without intersecting triangles, European J. Combin. 33 (2012), no. 5, 905--923.
I. Choi, Toroidal graphs containing neither K􀀀5 nor 6-cycles are 4-choosable, arXiv:1307.3293v1, [math.CO], 2013.
I. Choi and H. Zhang, Vertex arboricity of toroidal graphs with a forbidden cycle, Discrete Math. 333 (2014) 101--105.
 R. J. Cook, Point-arboricity and girth, J. Lond. Math. Soc. (2) 8 (1974) 322--324.
 P. Erdos, A. L. Rubin and H. Taylor, Choosability in graphs, in: Proc. West Coast Conference on Combinatorics, Graph Theory and Computing, Arcata, 1979, Congress. Numer. Utilitas Math., Winnipeg, 1980.
M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman and Company, New York, 1979.
W. Goddard, Acyclic colorings of planar graphs, Discrete Math. 91 (1991), no. 1, 91--94.
B. Grunbaum, Acyclic colorings of planar graphs, Israel J. Math. 14 (1973) 390--408.
S. L. Hakimi and E. F. Schmeichel, A note on the vertex arboricity of a graph, SIAM J. Discrete Math. (2) 2 (1989) 64--67.
D. Huang, W. C. Shiu and W. Wang, On the vertex-arboricity of planar graphs without 7-cycles, Discrete Math. 312 (2012), no. 15, 2304--2315.
H. V. Kronk, An analogue to the Heawood map-colouring problem, J. Lond. Math. Soc. (2) 1 (1969) 750--752.
H. V. Kronk and J. Mitchem, Critical point-arboritic graphs, J. Lond. Math. Soc. (2) 9 (1975) 459--466.
M. Matsumoto, Bounds for the vertex linear arboricity, J. Graph Theory 14 (1990), no. 1, 117--126.
K. S. Poh, On the linear vertex-arboricity of a planar graph, J. Graph Theory 14 (1990), no. 1, 73--75.
A. Raspaud, W. Wang, On the vertex-arboricity of planar graphs, European J. Combin. 29 (2008), no. 4, 1064--1075.
P. D. Seymour, A note on list arboricity, J. Combin. Theory Ser. B 72 (1998), no. 1, 150--151.
R. _Skrekovski, On the critical point-arboricity graphs, J. Graph Theory 39 (2002), no. 1, 50--61.
S. K. Stein, B-Sets and planar maps, Paci_c. J. Math. 37 (1971) 217--224.
V. G. Vizing, Coloring the vertices of a graph in prescribed colors, (Russian) Metody Diskret. Anal. 29 (1976) 3--10.
J. Wang, On point-linear arboricity of planar graphs, Discrete Math. 72 (1988), no. 1-3, 381--384.
W. Wang and K. Lih, Choosability and edge choosability of planar graphs without  vecycles, Appl. Math. Lett. 15 (2002), no. 5, 561--565.
N. Xue, B. Wu, List point arboricity of graphs, Discrete Math. Algorithms Appl. 4 (2012), no. 2, 1--10.
A. Yang and J. Yuan, On the vertex arboricity of planar graphs of diameter two, Discrete Math. 307 (2007)), no. 19-20, 2438--2447.
L. Zhen and B. Wu, List point arboricity of dense graphs, Graphs Combin. 25 (2009), no. 1, 123--128.
Bulletin of the Iranian Mathematical Society
Volume 42, Issue 5 - Serial Number 5
October 2016
Pages 1293-1303

Files

History

  • Receive Date: 08 December 2013
  • Revise Date: 19 August 2015
  • Accept Date: 19 August 2015

Share

How to cite

Statistics