(a, b)-decomposition

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 \geq 4$ .^[2]
- (1, 4)-decomposable if $g \geq 5$ .^[3]
- F(1, 2)-decomposable if $g \geq 6$ .^[4]
- F(1, 1)-decomposable if $g \geq 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

↑ Template:Harvtxt, conjectured by Template:Harvtxt. Improving results by Template:Harvtxt then Template:Harvtxt.
↑ ^2.0 ^2.1 Implied by Template:Harvtxt.
↑ Template:Harvtxt
↑ Implied by Template:Harvtxt, improving results by Template:Harvtxt, then Template:Harvtxt.
↑ 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.
↑ Template:Harvtxt, even if not explicitly stated.
↑ Template:Harvtxt, improving results by Template:Harvtxt, then Template:Harvtxt.
↑ Proved without explicit reference by Template:Harvtxt.

[1] Template:Harvtxt, conjectured by Template:Harvtxt. Improving results by Template:Harvtxt then Template:Harvtxt.

[NW-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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

(a, b)-decomposition

Graph classes

Notes

References (chronological order)

Navigation menu

Search