Abstract
Astar forest is a forest all of whose components are stars. Thestar arboricity, st(G) of a graphG is the minimum number of star forests whose union covers all the edges ofG. Thearboricity, A(G), of a graphG is the minimum number of forests whose union covers all the edges ofG. Clearlyst(G)≥A(G). In fact, Algor and Alon have given examples which show that in some casesst(G) can be as large asA(G)+Ω(logΔ) (where Δ is the maximum degree of a vertex inG). We show that for any graphG, st(G)≤A(G)+O(logΔ).
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
J. Akiyama andM. Kano: Path factors of a graph, in:Graph Theory and its Applications, Wiley and Sons, New York, 1984.
Ilan Algor andNoga Alon: The star arboricity of graphs,Discrete Math.,75 (1989), 11–22.
Y. Aoki: The star arboricity of the complete regular multipartite graphs, preprint.
P. Erdős andL. Lovász: Problems and results on 3-chromatic hypergraphs and some related question, in:Infinite and Finite Sets, A. Hajnal et al. editors, North Holland, Amsterdam, 1975, 609–628.
C. St. J. A. Nash-Williams: Decomposition of finite graphs into forests,J. London Math. Soc. 39 (1964), 12.