# (a,b) decomposability

Updated on
Covid-19

In graph theory, the (ab)-decomposability of an undirected graph is the existence of a partition of its edges into a + 1 sets, each one of them inducing a forest, except one who induces a graph with maximum degree b. If this graph is also a forest, then we call this a F(ab)-decomposition.

A graph with arboricity a is (a, 0)-decomposable. Every (a0)-decomposition or (a1)-decomposition is a F(a0)-decomposition or a F(a1)-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 4 .
• (1,4)-decomposable if g 5 .
• F(1,2)-decomposable if g 6 .
• F(1,1)-decomposable if g 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.
• ## References

(a,b)-decomposability Wikipedia

Topics