(a, b)-decomposition

From testwiki
Jump to navigation Jump to search

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

Notes

Template:Reflist

References (chronological order)

Template:Refbegin

Template:Refend

  1. ↑ Template:Harvtxt, conjectured by Template:Harvtxt. Improving results by Template:Harvtxt then Template:Harvtxt.
  2. ↑ 2.0 2.1 Implied by Template:Harvtxt.
  3. ↑ Template:Harvtxt
  4. ↑ Implied by Template:Harvtxt, improving results by Template:Harvtxt, then Template:Harvtxt.
  5. ↑ Independently proved by Template:Harvtxt and implied by Template:Harvtxt, improving results by Template:Harvtxt for girth 11, then Template:Harvtxt for girth 10 and Template:Harvtxt for girth 9.
  6. ↑ Template:Harvtxt, even if not explicitly stated.
  7. ↑ Template:Harvtxt, improving results by Template:Harvtxt, then Template:Harvtxt.
  8. ↑ Proved without explicit reference by Template:Harvtxt.
Retrieved from "https://en.wiki.beta.math.wmflabs.org/w/index.php?title=(a,_b)-decomposition&oldid=38858"