On the critical point‐arboricity graphs
Riste Škrekovski · Journal of Graph Theory · 2001
Abstract In this paper, we study the critical point‐arboricity graphs. We prove two lower bounds for the number of edges of k‐critical point‐arboricity graphs. A theorem of Kronk is extended by proving that the point‐arboricity of a graph G embedded on a surface S with Euler genus g = 2, 5, 6 or g ≥ 10 is at most $k =\lfloor {9 +\sqrt {1+ 24\, g}\over 4}\rfloor$ with equality holding iff G contains either K2k−1 or K2k−4 + C5 as a subgraph. It is also proved that locally planar graphs have point‐arboricity ≤ 3 and that triangle‐free locally planar‐graphs have point‐arboricity ≤ 2. © 2002 John Wiley & Sons, Inc. J Graph Theory 39: 50–61, 2002