Star arboricity

DOI10.1007/BF01305230MaRDI QIDQ1204531zbMATH OpenOpenAlexFDO

Authors Noga Alon, Colin McDiarmid, Bruce Reed

Publication date 10 March 1993

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01305230

zbMATH Keywords

arboricitystar arboricitystar forest

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Combinatorial probability (60C05)

Review text

\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)\).

Recommendations

• scientific article; zbMATH DE number 1229625
• Star arboricity of graphs
• Quadratic Starlike Trees
• On star and caterpillar arboricity
• Stars on trees
• scientific article; zbMATH DE number 125471
• The star arboricity of graphs
• Starlike trees are determined by their Laplacian spectrum
• The starlike trees which span a hypercube
• scientific article; zbMATH DE number 1823807

Cites work

• Decomposition of Finite Graphs Into Forests
• The star arboricity of graphs
• The star-arboricity of the complete regular multipartite graphs

Cited in

(30)

• Probabilistic methods in coloring and decomposition problems
• On incidence coloring and star arboricity of graphs
• Induced and weak induced arboricities
• On incidence coloring of complete multipartite and semicubic bipartite graphs
• The star arboricity of graphs
• Star arboricity of graphs
• Local and union page numbers
• Interval incidence graph coloring
• Regularity of symbolic powers and arboricity of matroids
• On nowhere dense graphs
• Edge-intersection graphs of grid paths: the bend-number
• Tree-depth, subgraph coloring and homomorphism bounds
• Interval incidence coloring of bipartite graphs
• A note on incidence graphs
• WDM and directed star arboricity
• On globally sparse Ramsey graphs
• scientific article; zbMATH DE number 125471 (Why is no real title available?)
• Astral graphs (threshold graphs), scale-free graphs and related algorithmic questions
• scientific article; zbMATH DE number 1229625 (Why is no real title available?)
• Stars on trees
• Interval incidence coloring of subcubic graphs
• On edge star sets in trees
• On the chromatic number of powers of subdivisions of graphs
• On first-order transductions of classes of graphs
• Decomposition of geometric graphs into star-forests
• Star-forest decompositions of complete graphs
• Partition density, star arboricity, and sums of Laplacian eigenvalues of graphs
• Graph factors and factorization: 1985--2003: a survey
• On low tree-depth decompositions
• Three ways to cover a graph

This page was built for publication: Star arboricity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1204531)