TY - JOUR
T1 - The Star Arboricity of Graphs
AU - Algor, I.
AU - Alon, N.
N1 - Funding Information:
* Research supported in part by Allon Binational Science Foundation.
Funding Information:
Fellowship and by a grant from the United States Israel
PY - 1989/1/1
Y1 - 1989/1/1
N2 - 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/4d +O(d 2/3(log d)1/3), and that there are d-regular graphs G with st(G) > 1/2d + Ω(log d). 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.
AB - 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/4d +O(d 2/3(log d)1/3), and that there are d-regular graphs G with st(G) > 1/2d + Ω(log d). 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.
UR - http://www.scopus.com/inward/record.url?scp=77957079042&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77957079042&partnerID=8YFLogxK
U2 - 10.1016/S0167-5060(08)70561-2
DO - 10.1016/S0167-5060(08)70561-2
M3 - Article
AN - SCOPUS:77957079042
SN - 0167-5060
VL - 43
SP - 11
EP - 22
JO - Annals of Discrete Mathematics
JF - Annals of Discrete Mathematics
IS - C
ER -