Arboricity and Star Arboricity of Graphs

Authors:

• Andrzej Kurek

Abstract

The arboricity A(G) of the graph G is the minimum number of forests whose union covers all edges of G. A star forest is a forest in which every connected component is a star. The star arboricity st(G) of a graph G is the minimum number of star forests whose union covers all edges of G. Since every tree can be decomposed into two star forests, st(G)≤2A(G) for every graph G. In [1] the question about the maximum star arboricity of a graph with given arboricity was posed. We show that for any k there exists a graph with A(G) = k and st(G) = 2k. The same result was obtained independently by Alon, McDiarmid and Reed (see [2]). © 1992, Academic Press, Inc. All rights reserved.