Abstract
A star forest is a forest whose connected components are stars. The star arboricity st(G) of a graph G is the minimum number of star forests whose union covers all edges of G. We show that for every d-regular graph G, 1 2d<st(G)≤ 1 2d + O(d 2 3(logd) 1 3, and that there are d-regular graphs G with st(G)> 1 2d + omega;(logd). We also observe that the star arboricity of any planar graph is at most 6 and that there are planar graphs whose star arboricity is at least 5.
Original language | English (US) |
---|---|
Pages (from-to) | 11-22 |
Number of pages | 12 |
Journal | Discrete Mathematics |
Volume | 75 |
Issue number | 1-3 |
DOIs | |
State | Published - May 1989 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics