The star arboricity of graphs

I. Algor, N. Alon

Research output: Contribution to journalArticlepeer-review

61 Scopus citations

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 languageEnglish (US)
Pages (from-to)11-22
Number of pages12
JournalDiscrete Mathematics
Volume75
Issue number1-3
DOIs
StatePublished - May 1989
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'The star arboricity of graphs'. Together they form a unique fingerprint.

Cite this