In graph theory, the (a, b)-decomposition of an undirected graph is a partition of its edges into a + 1 sets, each one of them inducing a forest, except one which induces a graph with maximum degree b. If this graph is also a forest, then we call this a F(a, b)-decomposition.
A graph with arboricity a is (a, 0)-decomposable. Every (a, 0)-decomposition or (a, 1)-decomposition is a F(a, 0)-decomposition or a F(a, 1)-decomposition respectively.
Graph classes
Every planar graph is F(2, 4)-decomposable., conjectured by . Improving results by then . Every planar graph with girth at least is F(2, 0)-decomposable if .Implied by . (1, 4)-decomposable if . F(1, 2)-decomposable if .Implied by , improving results by , then . F(1, 1)-decomposable if ,Independently proved by and implied by , improving results by for girth 11, then for girth 10 and for girth 9. or if every cycle of is either a triangle or a cycle with at least 8 edges not belonging to a triangle., even if not explicitly stated. (1, 5)-decomposable if has no 4-cycles., improving results by , then . Every outerplanar graph is F(2, 0)-decomposable and (1, 3)-decomposable.Proved without explicit reference by .
Notes
References (chronological order)