## Abstract

A forest decomposition of a multigraph G is a family of edge-disjoint subforests of G whose edge sets cover all edges of G. The minimum number of forests in a forest decomposition of G is called the arboricity of G is denoted by Y(G). The well-known result of Nash-Williams states that Y(G)=max{⌈ |E(h)| |V(H)|-1⌉}, where the maximum is taken over all induced subgraphs H of G with at least two vertices. A natural question arises: How does the Nash-Williams formula change if forests to be used in decompositions have maximum degrees bounded by a given integer d? The minimum number of such forests necessary to decompose G will be denoted by Y_{d}(G). In this paper we propose and study the following conjecture: For every multigraph G and for every d≥2, Y_{d}(G)= Δ(G) d or Δ(G) d+1 if Y(G)= Δ(G) d, maxY(G), Δ(G) d otherwise. otherwise. We show that the conjecture is true in the case when d≥Δ(G)+1-Y(G) and also for complete multigraphs K^{(λ)}_{n} and complete bipartite multigraphs K^{(λ)}_{m,n}. In the case when d=2 and G is regular our conjecture reduces to Y_{2}(G)=Y(G) and generalizes the Linear Arboricity Conjecture.

Original language | English |
---|---|

Pages (from-to) | 207-222 |

Number of pages | 16 |

Journal | Discrete Mathematics |

Volume | 98 |

Issue number | 3 |

DOIs | |

State | Published - Dec 26 1991 |

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics