(a,b) decomposability - Alchetron, The Free Social Encyclopedia

In graph theory, the (a, b)-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(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 ≥ 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

(Text) CC BY-SA