Article
Full entry | Fulltext not available
(moving wall
24 months)
Feedback
Keywords:
planar graph; vertex-arboricity; forest; vertex partition
planar graph; vertex-arboricity; forest; vertex partition
Summary:
It was known that the vertex set of every planar graph can be partitioned into three forests. We prove that the vertex set of a planar graph without chordal 5-cycles can be partitioned into two forests. This extends a result obtained by Raspaud and Wang in 2008.
References:
[1] Borodin, O. V., Ivanova, A. O.: Planar graphs without 4-cycles adjacent to 3-cycles are list vertex 2-arborable. J. Graph Theory 62 (2009), 234-240. DOI 10.1002/jgt.20394 | MR 2566928 | Zbl 1180.05035
[2] Chartrand, G., Kronk, H. V.: The point-arboricity of planar graphs. J. Lond. Math. Soc. 44 (1969), 612-616. DOI 10.1112/jlms/s1-44.1.612 | MR 0239996 | Zbl 0175.50505
[3] Chartrand, G., Kronk, H. V., Wall, C. E.: The point-arboricity of a graph. Isr. J. Math. 6 (1968), 169-175. DOI 10.1007/BF02760181 | MR 0236049 | Zbl 0164.54201
[4] Chen, M., Raspaud, A., Wang, W.: Vertex-arboricity of planar graphs without intersecting triangles. Eur. J. Comb. 33 (2012), 905-923. DOI 10.1016/j.ejc.2011.09.017 | MR 2889524 | Zbl 1250.05062
[5] Garey, M. R., Johnson, D. S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York (1979). MR 0519066 | Zbl 0411.68039
[6] Hakimi, S. L., Schmeichel, E. F.: A note on the vertex arboricity of a graph. SIAM J. Discrete Math. 2 (1989), 64-67. DOI 10.1137/0402007 | MR 0976789 | Zbl 0684.05028
[7] Huang, D., Shiu, W. C., Wang, W.: On the vertex-arboricity of planar graphs without 7-cycles. Discrete Math. 312 (2012), 2304-2315. DOI 10.1016/j.disc.2012.03.035 | MR 2926103 | Zbl 1245.05029
[8] Huang, D., Wang, W.: Vertex arboricity of planar graphs without chordal 6-cycles. Int. J. Comput. Math. 90 (2013), 258-272. DOI 10.1080/00207160.2012.727989 | MR 3016834 | Zbl 1278.05100
[9] Raspaud, A., Wang, W.: On the vertex-arboricity of planar graphs. Eur. J. Comb. 29 (2008), 1064-1075. DOI 10.1016/j.ejc.2007.11.022 | MR 2408378 | Zbl 1144.05024
[10] Stein, S. K.: $B$-sets and planar maps. Pac. J. Math. 37 (1971), 217-224. DOI 10.2140/pjm.1971.37.217 | MR 0306053 | Zbl 0194.56101
[11] Wang, Y., Wang, Y., Lih, K.-W.: Partitioning kite-free planar graphs into two forests. J. Graph Theory 106 (2024), 30-56. DOI 10.1002/jgt.23062 | MR 4730107 | Zbl 7823339
Search
Partner of
