In graph theory, the star arboricity of a graph 
, sometimes denoted 
, is the minimum number of star forests whose union covers
all edges of 
.
Equivalently, it is the minimum number of edge-disjoint star forests into which the
edges of 
can be partitioned. Here, a star forest is a forest each
of whose connected components is a star graph 
. The notion was introduced by
Algor and Alon (1989).
If 
denotes the arboricity of 
, then
 |
The lower bound is immediate since every star forest is a forest. The upper bound follows from the fact that every tree can
be decomposed into two star forests, for example by rooting the tree and splitting
its edges according to parity of level. In particular, 
iff 
is itself a star forest.
Algor and Alon (1989) showed that every planar graph has star arboricity at most 6 and that there exist planar graphs with star arboricity at least 5. Hakimi, Mitchem, and Schmeichel later proved that every planar graph has star arboricity at most 5, settling the planar case. They also showed that deciding whether a graph has star arboricity 2 is NP-complete.
