Covering regular graphs with forests of small trees

H. Assiyatun, N. C. Wormald

Research output: Contribution to journalArticleResearchpeer-review

1 Citation (Scopus)

Abstract

A (d, k) -forest is a forest consisting of trees whose diameters are at most d and whose maximum vertex degree,Δ is at most k. The (d, k)-arboricity of a graph G is the minimum number of (d, k)-forests needed to cover E(G). This concept is a common generalization of linear k-arboricity and star arboricity. Using a probabilistic approach developed recently for linear karboricity, we obtain an upper bound on the (d, k)-arboricity of r-regular graphs.

Original languageEnglish
Pages (from-to)219-226
Number of pages8
JournalAustralasian Journal of Combinatorics
Volume22
Publication statusPublished - 2000
Externally publishedYes

Cite this