The star arboricity of graphs (Q1825208)

The star arboricity st(G) of a graph G is the minimum number of star forests the union of which covers all edges of G. (A star forest is a graph every component of which is a star.) For a d-regular graph G an upper and lower bound of st(G) are given: \[ 1/2d\leq st(G)\leq 1/2d+O(d^{2/3}(\log d)^{1/3}). \] The number \(1/2d+\Omega (\log d)\) is not an upper bound of st(G). Finally, for a planar graph G, st(G) is at most 6 and there are planar graphs G with st(G) at least 5.