(a, b)-decomposition

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.^[1]
• Every planar graph ${\displaystyle G}$ with girth at least ${\displaystyle g}$ is
  • F(2, 0)-decomposable if ${\displaystyle g\geq 4}$.^[2]
  • (1, 4)-decomposable if ${\displaystyle g\geq 5}$.^[3]
  • F(1, 2)-decomposable if ${\displaystyle g\geq 6}$.^[4]
  • F(1, 1)-decomposable if ${\displaystyle g\geq 8}$,^[5] or if every cycle of ${\displaystyle G}$ is either a triangle or a cycle with at least 8 edges not belonging to a triangle.^[6]
  • (1, 5)-decomposable if ${\displaystyle G}$ has no 4-cycles.^[7]
• Every outerplanar graph is F(2, 0)-decomposable^[2] and (1, 3)-decomposable.^[8]