Star arboricity (Q1204531): Difference between revisions

\textit{C. St. J. A. Nash-Williams} [J. Lond. Math. Soc. 39, 12 (1964; Zbl 0119.388)] defined the arboricity of a graph \(G\), shortly \(A(G)\), as the minimum number of forests needed to cover all edges of \(G\). By a star forest the authors mean a forest all of whose components are stars. J. Akiyama and M. Kano introduced the star arboricity of \(G\), denoted \(\text{st}(G)\), as follows: \(\text{st}(G)\) is the minimum number of star forests whose union covers all edges of \(G\). Let \(\Delta\) be the minimum degree of a vertex in \(G\). In the paper under review it is shown that for any graph \(G\), \(\text{st}(G)\leq A(G)+O(\log \Delta)\).