Factorisation of regular graphs into forests of short paths

Terri Lindquester, Nicholas C. Wormald

Research output: Contribution to journalArticleResearchpeer-review

Abstract

The k-linear arboricity of a graph G is the minimum number of forests whose connected components are paths of length at most k which partition E(G). Motivated by this index, we investigate a variation of this idea for d-regular graphs. Namely, we define a d-regular graph G to be (l, k)-linear arborific if E(G) can be partitioned into edge sets of l linear forests consisting of paths of length at most k. By extending an inductive tool developed by Jackson and Wormald, we determine, for d ≥ 4, values of k such that every d-regular graph is (d - l, k)-linear arborific.

Original languageEnglish
Pages (from-to)217-226
Number of pages10
JournalDiscrete Mathematics
Volume186
Issue number1-3
Publication statusPublished - 15 May 1998
Externally publishedYes

Cite this