zbMATH — the first resource for mathematics

Star arboricity. (English) Zbl 0780.05043
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)\).

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
60C05 Combinatorial probability
Full Text: DOI
[1] J. Akiyama andM. Kano: Path factors of a graph, in:Graph Theory and its Applications, Wiley and Sons, New York, 1984.
[2] Ilan Algor andNoga Alon: The star arboricity of graphs,Discrete Math.,75 (1989), 11-22. · Zbl 0684.05033 · doi:10.1016/0012-365X(89)90073-3
[3] Y. Aoki: The star arboricity of the complete regular multipartite graphs, preprint. · Zbl 0737.05038
[4] 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.
[5] C. St. J. A. Nash-Williams: Decomposition of finite graphs into forests,J. London Math. Soc. 39 (1964), 12. · Zbl 0119.38805 · doi:10.1112/jlms/s1-39.1.12
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.