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.
- Every planar graph with girth at least is
- F(2, 0)-decomposable if .
- (1, 4)-decomposable if .
- F(1, 2)-decomposable if .
- F(1, 1)-decomposable if , or if every cycle of is either a triangle or a cycle with at least 8 edges not belonging to a triangle.
- (1, 5)-decomposable if has no 4-cycles.
- Every outerplanar graph is F(2, 0)-decomposable and (1, 3)-decomposable.
Notes
References (chronological order)