(a, b)-decomposition explained

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]

G with girth at least g is

• • F(2, 0)-decomposable if

g \ge 4 .^[2]

• • (1, 4)-decomposable if

g \ge 5 .

• • F(1, 2)-decomposable if

g \ge 6 .^[3]

• • F(1, 1)-decomposable if

g \ge 8 ,^[4] or if every cycle of G is either a triangle or a cycle with at least 8 edges not belonging to a triangle.^[5]

• • (1, 5)-decomposable if

G has no 4-cycles.^[6]

• Every outerplanar graph is F(2, 0)-decomposable and (1, 3)-decomposable.^[7]

References (chronological order)

• Nash-Williams. Crispin St. John Alvah. Decomposition of finite graphs into forests. Journal of the London Mathematical Society. 39. 1. 1964. 12. 10.1112/jlms/s1-39.1.12. 0161333.
• Guan. D. J.. Zhu. Xuding. 1999. Game chromatic number of outerplanar graphs. Journal of Graph Theory. 30. 1. 67–70. 10.1002/(sici)1097-0118(199901)30:1<67::aid-jgt7>3.0.co;2-m.
• He. Wenjie. Hou. Xiaoling. Lih. Ko-Wei. Shao. Jiating. Wang. Weifan. Zhu. Xuding. 2002. Edge-partitions of planar graphs and their game coloring numbers. Journal of Graph Theory. 41. 4. 307–311. . 10.1002/jgt.10069. 20929383. free.
• Balogh. József. Kochol. Martin. Pluhár. András . Yu. Xingxing. 2005. Covering planar graphs with forests. Journal of Combinatorial Theory, Series B. 94. 1. 147–158. . 10.1016/j.ejc.2007.06.020. free.
• Borodin. Oleg V.. Kostochka. Alexandr V. . Sheikh. Naeem N. . Yu. Gexin. 2008. Decomposing a planar graph with girth 9 into a forest and a matching. European Journal of Combinatorics. 29. 5. 1235–1241. . 10.1016/j.ejc.2007.06.020. free.
• Borodin. Oleg V.. Kostochka. Alexandr V. . Sheikh. Naeem N. . Yu. Gexin. 2008. M-Degrees of Quadrangle-Free Planar Graphs. Journal of Graph Theory. 60. 1. 80–85. . 10.1002/jgt.20346. 10.1.1.224.8397. 7486622.
• Kleitman. Daniel J. . 2008. Partitioning the Edges of a Girth 6 Planar Graph into those of a Forest and those of a Set of Disjoint Paths and Cycles. Manuscript.
• Gonçalves. Daniel. 2009. Covering planar graphs with forests, one having bounded maximum degree. Journal of Combinatorial Theory, Series B. 99. 2. 314–322. 10.1016/j.jctb.2008.07.004. free.
• Borodin. Oleg V.. Ivanova. Anna O.. Kostochka. Alexandr V. . Sheikh. Naeem N. . 2009. Decompositions of Quadrangle-Free Planar Graphs. Discussiones Mathematicae Graph Theory. 29. 87–99. . 10.7151/dmgt.1434. 10.1.1.224.8787.
• Borodin. Oleg V.. Ivanova. Anna O.. Kostochka. Alexandr V. . Sheikh. Naeem N. . 2009. Planar graphs decomposable into a forest and a matching. Discrete Mathematics. 309. 1. 277–279. . 10.1016/j.disc.2007.12.104. free.
• Bassa. A.. Burns. J.. Campbell. J.. Deshpande. A. . Farley. J. . Halsey. L. . Ho. S.-Y. . Kleitman. D. . Michalakis. S. . Persson. P.-O. . Pylyavskyy. P. . Rademacher. L. . Riehl. A. . Rios. M. . Samuel. J. . Tenner. B.E. . Vijayasarathy. A. . Zhao. L. . 2010. Partitioning a Planar Graph of Girth 10 into a Forest and a Matching. European Journal of Combinatorics. 124. 3. 213–228. . 10.1111/j.1467-9590.2009.00468.x. 120663098.
• Wang. Yingqian. Zhang. Qijun. 2011. Decomposing a planar graph with girth at least 8 into a forest and a matching. Discrete Mathematics. 311. 10–11. 844–849. 10.1016/j.disc.2011.01.019. free.
• Montassier. Mickaël. Ossona de Mendez. Patrice . Patrice Ossona de Mendez. André. Raspaud. Zhu. Xuding. 2012. Decomposing a graph into forests. Journal of Combinatorial Theory, Series B. 102. 1. 38–52. . 10.1016/j.jctb.2011.04.001. free.

Notes and References

1. , conjectured by . Improving results by then .
2. Implied by .
3. Implied by, improving results by, then .
4. Independently proved by and implied by, improving results by for girth 11, then for girth 10 and for girth 9.
5. , even if not explicitly stated.
6. , improving results by, then .
7. Proved without explicit reference by .