(a,b)-decomposability

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 $G$ with girth at least $g$ is
** F(2, 0)-decomposable if $g \ge 4$.Implied by .
** (1, 4)-decomposable if $g \ge 5$.
** F(1, 2)-decomposable if $g \ge 6$.
** F(1, 1)-decomposable if $g \ge 8$, or if every cycle of $G$ is either a triangle or a cycle with at least 8 edges not belonging to a triangle.
** (1, 5)-decomposable if $G$ has no 4-cycles.
* Every outerplanar graph is F(2, 0)-decomposable and (1, 3)-decomposable.Proved without explicit reference by .

Notes

References (chronological order)

*
*
*
*
*
*
*
*
*
*
*
*
*
{{refend

Graph invariants
Graph theory objects