Puneet Varma (Editor)

(a,b) decomposability

Updated on
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

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