(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

^ Gonçalves (2009), conjectured by Balogh et al. (2005). Improving results by Nash-Williams (1964) then Balogh et al. (2005).
^ ^a ^b Implied by Nash-Williams (1964).
^ He et al. (2002)
^ Implied by Montassier et al. (2012), improving results by He et al. (2002), then Kleitman (2008).
^ Independently proved by Wang & Zhang (2011) and implied by Montassier et al. (2012), improving results by He et al. (2002) for girth 11, then Bassa et al. (2010) for girth 10 and Borodin et al. (2008a) for girth 9.
^ Borodin et al. (2009b), even if not explicitly stated.
^ Borodin et al. (2009a), improving results by He et al. (2002), then Borodin et al. (2008b).
^ Proved without explicit reference by Guan & Zhu (1999).

References (chronological order)

Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).

[1] Gonçalves (2009), conjectured by Balogh et al. (2005). Improving results by Nash-Williams (1964) then Balogh et al. (2005).

[NW-2] Implied by Nash-Williams (1964).

[3] He et al. (2002)

[4] Implied by Montassier et al. (2012), improving results by He et al. (2002), then Kleitman (2008).

[5] Independently proved by Wang & Zhang (2011) and implied by Montassier et al. (2012), improving results by He et al. (2002) for girth 11, then Bassa et al. (2010) for girth 10 and Borodin et al. (2008a) for girth 9.

[6] Borodin et al. (2009b), even if not explicitly stated.

[7] Borodin et al. (2009a), improving results by He et al. (2002), then Borodin et al. (2008b).

[8] Proved without explicit reference by Guan & Zhu (1999).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

(a, b)-decomposition

Graph classes

Notes

References (chronological order)

Navigation menu

Search