The star arboricity of graphs
type: Item
instance of: scholarly article
title: The star arboricity of graphs
zbMATH Open document ID: 0684.05033
DOI: 10.1016/0012-365X(89)90073-3
author: I. Algor
author: Noga Alon
published in: Discrete Mathematics
publication date: 1989-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 4120204
zbMATH Keywords: algorithm
zbMATH Keywords: probability space
zbMATH Keywords: star arboricity
zbMATH Keywords: d-regular graph
reviewed by: Marie Demlová
MaRDI profile type: Publication
cites work: The linear arboricity of graphs
cites work: Q3907606
cites work: Covering and packing in graphs IV: Linear arboricity
cites work: Q3743338
cites work: The star-arboricity of the complete regular multipartite graphs
cites work: Q3682518
cites work: Q3941433
cites work: Graphs which contain all small graphs
cites work: Q4074927
cites work: The linear arboricity of some regular graphs
cites work: Q3752419
cites work: A Constructive Solution to a Tournament Problem
cites work: Q3903002
cites work: Decomposition of Finite Graphs Into Forests
cites work: Q3956983
full work available at URL: 0012-365x(89)90073-3
OpenAlex ID: W2128081519
description: scientific article; zbMATH DE number 4120204