On Decomposing Graphs Into Forests and Pseudoforests

Abstract: We prove that for

k i n m a t h b b N

and

d l e q 2 k + 2

, if a graph has maximum average degree at most

2 k + f r a c 2 d d + k + 1

, then

G

decomposes into

k + 1

pseudoforests, where one of the pseudoforests has all connected components having at most

d

edges.

This page was built for publication: On Decomposing Graphs Into Forests and Pseudoforests