Decompositions of graphs into forests with bounded maximum degree

Mirosław Truszczyński

Research output: Contribution to journalArticlepeer-review

4 Scopus citations


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 Yd(G). In this paper we propose and study the following conjecture: For every multigraph G and for every d≥2, Yd(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 Y2(G)=Y(G) and generalizes the Linear Arboricity Conjecture.

Original languageEnglish
Pages (from-to)207-222
Number of pages16
JournalDiscrete Mathematics
Issue number3
StatePublished - Dec 26 1991

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Decompositions of graphs into forests with bounded maximum degree'. Together they form a unique fingerprint.

Cite this