(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.
Every planar graph G girth at least g F(2, 0)-decomposable if g ≥ 4
(1, 4)-decomposable if g ≥ 5
F(1, 2)-decomposable if g ≥ 6
F(1, 1)-decomposable if g ≥ 8 G
(1, 5)-decomposable if G
Every outerplanar graph is F(2, 0)-decomposable and (1, 3)-decomposable.
Nash-Williams, Crispin St. John Alvah (1964). "Decomposition of finite graphs into forests". Journal of the London Mathematical Society 39 (1): 12. doi :10.1112/jlms/s1-39.1.12 . MR 0161333 . Guan, D. J.; Zhu, Xuding (1999). "Game chromatic number of outerplanar graphs". Journal of Graph Theory . 30 (1): 67– 70. doi :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. doi :10.1002/jgt.10069 S2CID 20929383 . 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. doi :10.1016/j.ejc.2007.06.020 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. doi :10.1016/j.ejc.2007.06.020 Borodin, Oleg V.; Kostochka, Alexandr V.; Sheikh, Naeem N.; Yu, Gexin (2008). "M -Degrees of Quadrangle-Free Planar Graphs" (PDF) . Journal of Graph Theory . 60 (1): 80– 85. doi :10.1002/jgt.20346 . S2CID 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. doi :10.1016/j.jctb.2008.07.004 Borodin, Oleg V.; Ivanova, Anna O.; Kostochka, Alexandr V.; Sheikh, Naeem N. (2009). "Decompositions of Quadrangle-Free Planar Graphs" (PDF) . Discussiones Mathematicae Graph Theory . 29 : 87– 99. doi :10.7151/dmgt.1434 . 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. doi :10.1016/j.disc.2007.12.104 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. doi :10.1111/j.1467-9590.2009.00468.x . S2CID 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. doi :10.1016/j.disc.2011.01.019 Montassier, Mickaël; Ossona de Mendez, Patrice ; André, Raspaud; Zhu, Xuding (2012). "Decomposing a graph into forests" . Journal of Combinatorial Theory, Series B . 102 (1): 38– 52. doi :10.1016/j.jctb.2011.04.001