×

zbMATH — the first resource for mathematics

On the vertex-arboricity of planar graphs. (English) Zbl 1144.05024
The vertex-arboricity \(\alpha(G)\) of a graph \(G\) is the minimum number of parts in a partition of the vertices so that each part induces a forest. It is known that \(\alpha(G) \leq 3\) for any planar graph \(G\). In this paper the authors show that \(\alpha(G) \leq 2\) whenever \(G\) is planar and has no 4-cycles. They also show that \(\alpha(G) \leq 2\) if \(G\) is planar and any two triangles are of distance at least 3. The paper contains several nice conjectures about vertex-arboricity.

MSC:
05C10 Planar graphs; geometric and topological aspects of graph theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aldred, R.E.L.; Bau, S.; Holton, D.A.; Mckay, B.D., Nonhamiltonian 3-connected cubic planar graphs, SIAM J. discrete math., 13, 25-32, (2000) · Zbl 0941.05041
[2] Appel, K.; Haken, W., Every planar map is four colorable, Bull. amer. math. soc., 82, 711-712, (1976) · Zbl 0331.05106
[3] Borodin, O.V.; Glebov, A.N., On the partition of a planar graph of girth 5 into an empty and an acyclic subgraph, Diskretn. anal. issled. oper. ser.1, 8, 4, 34-53, (2001) · Zbl 1012.05133
[4] J. Bosák, Hamiltonian lines in cubic graphs, Presented at the International Seminar on Graph Theory and its Applications, Rome 5-9, 1966
[5] Burr, S.A., An inequality involving the vertex arboricity and the edge arborocity of a graph, J. graph theory, 10, 403-404, (1986) · Zbl 0651.05030
[6] Catlin, P.A.; Lai, H., Vertex arboricity and maximum degree, Discrete math., 141, 37-46, (1995) · Zbl 0827.05024
[7] Chang, G.J.; Chen, C.; Chen, Y., Vertex and tree arboricities of graphs, J. comb. optim., 8, 295-306, (2004) · Zbl 1055.05030
[8] Chartrand, G.; Kronk, H.V.; Wall, C.E., The point-arboricity of a graph, Israel J. math., 6, 169-175, (1968) · Zbl 0164.54201
[9] Chartrand, G.; Kronk, H.V., The point-arboricity of planar graphs, J. London math. soc., 44, 612-616, (1969) · Zbl 0175.50505
[10] Chen, Z.; He, X., Parallel complexity of partitioning a planar graph into vertex-induced forests, Discrete appl. math., 69, 183-198, (1996) · Zbl 0855.68040
[11] Choudum, S.A., Some 4-valent, 3-connected, planar, almost pancyclic graphs, Discrete math., 18, 125-129, (1977) · Zbl 0357.05040
[12] Cook, R.J., Point-arboricity and girth, J. London math. soc., 8, 2, 322-324, (1974) · Zbl 0286.05108
[13] Fijavž, G.; Juvan, M.; Mohar, B.; Škrekovski, R., Planar graphs without cycles of specific lengths, European J. combin., 23, 377-388, (2002) · Zbl 1001.05042
[14] Garey, M.R.; Johnson, D.S., Computers and intractability: A guide to the theory of NP-completeness, (1979), W.H. Freeman and Company New York · Zbl 0411.68039
[15] Grötzsch, H., Ein dreifarbensatz für dreikreisfrei netze auf der kugel, wiss. Z. martin-luther uni. halle-Wittenberg, Math. -nat. reihe, 8, 109-120, (1958)
[16] Hakimi, S.L.; Schmeichel, E.F., A note on the vertex arboricity of a graph, SIAM J. discrete math., 2, 64-67, (1989) · Zbl 0684.05028
[17] Hara, M.; Ohyama, Y.; Yamashita, S., On the linear vertex-arboricity of a surface, J. combin. math. combin. comput., 18, 3-10, (1995) · Zbl 0838.05037
[18] Holton, D.A.; Mckay, B.D., The smallest non-Hamiltonian 3-connected cubic planar graphs have 38 vertices, J. combin. theory ser. B, J. combin. theory ser. B, 47, 248-319, (1989), (erratum) · Zbl 0699.05035
[19] Lederberg, J., Systematics of organic molecules, graph topology and Hamiltonian circuits, instrumentation, Res. lab. rept. Stanford uni., 1040, (1966)
[20] Kronk, H.V., An analogue to the heawood map-coloring problem, J. London math. soc., 1, 2, 750-752, (1969) · Zbl 0184.27603
[21] Kronk, H.V.; Mitchem, J., Critical point arboritic graphs, J. London math. soc., 9, 459-466, (1974/75) · Zbl 0298.05132
[22] Poh, K.S., On the linear vertex-arboricity of a planar graph, J. graph theory, 14, 73-75, (1990) · Zbl 0705.05016
[23] S˘krekovski, R., On the critical point-arboricity graphs, J. graph theory, 39, 50-61, (2002) · Zbl 0994.05059
[24] Stein, S.K., B-set and planar maps, Pacific J. math., 37, 217-224, (1971) · Zbl 0194.56101
[25] Thomassen, C., Decomposing a planar graph into degenerate graphs, J. combin. theory ser. B, 65, 305-314, (1995) · Zbl 0840.05070
[26] Jianfang, Wang, On point-linear arboricity of planar graphs, Discrete math., 72, 381-384, (1988) · Zbl 0665.05010
[27] Weifan, Wang; Lih, Ko-Wei, Choosability and edge choosability of planar graphs without five cycles, Appl. math. lett., 15, 561-565, (2002) · Zbl 0994.05060
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.