(a, b)-decomposition


In graph theory, the -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-decomposition.
A graph with arboricity a is -decomposable. Every -decomposition or -decomposition is a F-decomposition or a F-decomposition respectively.

Graph classes

  • Every planar graph is F-decomposable.
  • Every planar graph with girth at least is
  • * F-decomposable if.
  • * -decomposable if.
  • * F-decomposable if.
  • * F-decomposable if, or if every cycle of is either a triangle or a cycle with at least 8 edges not belonging to a triangle.
  • * -decomposable if has no 4-cycles.
  • Every outerplanar graph is F-decomposable and -decomposable.