{{DISPLAYTITLE:(''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.<ref>{{harvtxt|Gonçalves|2009}}, conjectured by {{harvtxt|Balogh et al.|2005}}. Improving results by {{harvtxt|Nash-Williams|1964}} then {{harvtxt|Balogh et al.|2005}}.</ref> * Every planar graph <math>G</math> with girth at least <math>g</math> is ** F(2, 0)-decomposable if <math>g \ge 4</math>.<ref name=NW>Implied by {{harvtxt|Nash-Williams|1964}}.</ref> ** (1, 4)-decomposable if <math>g \ge 5</math>.<ref>{{harvtxt|He et al.|2002}}</ref> ** F(1, 2)-decomposable if <math>g \ge 6</math>.<ref>Implied by {{harvtxt|Montassier et al.|2012}}, improving results by {{harvtxt|He et al.|2002}}, then {{harvtxt|Kleitman|2008}}.</ref> ** F(1, 1)-decomposable if <math>g \ge 8</math>,<ref>Independently proved by {{harvtxt|Wang|Zhang|2011}} and implied by {{harvtxt|Montassier et al.|2012}}, improving results by {{harvtxt|He et al.|2002}} for girth 11, then {{harvtxt|Bassa et al.|2010}} for girth 10 and {{harvtxt|Borodin et al.|2008a}} for girth 9.</ref> or if every cycle of <math>G</math> is either a triangle or a cycle with at least 8 edges not belonging to a triangle.<ref>{{harvtxt|Borodin et al.|2009b}}, even if not explicitly stated.</ref> ** (1, 5)-decomposable if <math>G</math> has no 4-cycles.<ref>{{harvtxt|Borodin et al.|2009a}}, improving results by {{harvtxt|He et al.|2002}}, then {{harvtxt|Borodin et al.|2008b}}.</ref> * Every outerplanar graph is F(2, 0)-decomposable<ref name=NW /> and (1, 3)-decomposable.<ref>Proved without explicit reference by {{harvtxt|Guan|Zhu|1999}}.</ref>
== Notes ==
{{reflist|2}}
== References (chronological order) == {{refbegin}} *{{cite journal|last=Nash-Williams|first=Crispin St. John Alvah|title=Decomposition of finite graphs into forests|journal=Journal of the London Mathematical Society|volume=39|issue=1|year=1964|pages=12|doi=10.1112/jlms/s1-39.1.12|mr=0161333}} * {{cite journal | last1 = Guan | first1 = D. J. | last2 = Zhu | first2 = Xuding | date = 1999 | title = Game chromatic number of outerplanar graphs | journal = Journal of Graph Theory | volume = 30 | issue = 1 | pages = 67–70 | doi=10.1002/(sici)1097-0118(199901)30:1<67::aid-jgt7>3.0.co;2-m }} * {{cite journal | last1 = He | first1 = Wenjie | last2 = Hou | first2 = Xiaoling | last3 = Lih | first3 = Ko-Wei | last4 = Shao | first4 = Jiating | last5 = Wang | first5 = Weifan | last6 = Zhu | first6 = Xuding | date = 2002 | title = Edge-partitions of planar graphs and their game coloring numbers | journal = Journal of Graph Theory | volume = 41 | issue = 4 | pages = 307–311 | ref = {{harvid|He et al.|2002}} | doi = 10.1002/jgt.10069 | s2cid = 20929383 | doi-access= free }} * {{cite journal | last1 = Balogh | first1 = József | last2 = Kochol | first2 = Martin | last3 = Pluhár | first3 = András | last4 = Yu | first4 = Xingxing | date = 2005 | title = Covering planar graphs with forests | journal = Journal of Combinatorial Theory, Series B | volume = 94 | issue = 1 | pages = 147–158 | ref = {{harvid|Balogh et al.|2005}} | doi = 10.1016/j.ejc.2007.06.020 | doi-access= free }} * {{cite journal | last1 = Borodin | first1 = Oleg V. | last2 = Kostochka | first2 = Alexandr V. | last3 = Sheikh | first3 = Naeem N. | last4 = Yu | first4 = Gexin | date = 2008 | title = Decomposing a planar graph with girth 9 into a forest and a matching | journal = European Journal of Combinatorics | volume = 29 | issue = 5 | pages = 1235–1241 | ref = {{harvid|Borodin et al.|2008a}} | doi = 10.1016/j.ejc.2007.06.020 | doi-access= free }} * {{cite journal | last1 = Borodin | first1 = Oleg V. | last2 = Kostochka | first2 = Alexandr V. | last3 = Sheikh | first3 = Naeem N. | last4 = Yu | first4 = Gexin | date = 2008 | title = ''M''-Degrees of Quadrangle-Free Planar Graphs | url = http://www.math.uiuc.edu/~kostochk/docs/2012/jgt09bsy.pdf | journal = Journal of Graph Theory | volume = 60 | issue = 1 | pages = 80–85 | ref = {{harvid|Borodin et al.|2008b}} | doi = 10.1002/jgt.20346 | citeseerx = 10.1.1.224.8397 | s2cid = 7486622 }} * {{cite journal | last = Kleitman | first = Daniel J. | date = 2008 | title = Partitioning the Edges of a Girth 6 Planar Graph into those of a Forest and those of a Set of Disjoint Paths and Cycles | journal = Manuscript }} * {{cite journal | last = Gonçalves | first = Daniel | date = 2009 | title = Covering planar graphs with forests, one having bounded maximum degree | journal = Journal of Combinatorial Theory, Series B | volume = 99 | issue = 2 | pages = 314–322 | doi = 10.1016/j.jctb.2008.07.004 | doi-access= free }} * {{cite journal | last1 = Borodin | first1 = Oleg V. | last2 = Ivanova | first2 = Anna O. | last3 = Kostochka | first3 = Alexandr V. | last4 = Sheikh | first4 = Naeem N. | date = 2009 | title = Decompositions of Quadrangle-Free Planar Graphs | url = http://www.math.uiuc.edu/~kostochk/docs/2012/dmgt09bis.pdf | journal = Discussiones Mathematicae Graph Theory | volume = 29 | pages = 87–99 | ref = {{harvid|Borodin et al.|2009a}} | doi=10.7151/dmgt.1434 | citeseerx = 10.1.1.224.8787 }} * {{cite journal | last1 = Borodin | first1 = Oleg V. | last2 = Ivanova | first2 = Anna O. | last3 = Kostochka | first3 = Alexandr V. | last4 = Sheikh | first4 = Naeem N. | date = 2009 | title = Planar graphs decomposable into a forest and a matching | journal = Discrete Mathematics | volume = 309 | issue = 1 | pages = 277–279 | ref = {{harvid|Borodin et al.|2009b}} | doi=10.1016/j.disc.2007.12.104 | doi-access= free }} * {{cite journal | last1 = Bassa | first1 = A. | last2 = Burns | first2 = J. | last3 = Campbell | first3 = J. | last4 = Deshpande | first4 = A. | last5 = Farley | first5 = J. | last6 = Halsey | first6 = L. | last7 = Ho | first7 = S.-Y. | last8 = Kleitman | first8 = D. | last9 = Michalakis | first9 = S. | last10 = Persson | first10 = P.-O. | last11 = Pylyavskyy | first11 = P. | last12 = Rademacher | first12 = L. | last13 = Riehl | first13 = A. | last14 = Rios | first14 = M. | last15 = Samuel | first15 = J. | last16 = Tenner | first16 = B.E. |author16-link=Bridget Tenner | last17 = Vijayasarathy | first17 = A. | last18 = Zhao | first18 = L. | date = 2010 | title = Partitioning a Planar Graph of Girth 10 into a Forest and a Matching | journal = European Journal of Combinatorics | volume = 124 | issue = 3 | pages = 213–228 | ref = {{harvid|Bassa et al.|2010}} | doi = 10.1111/j.1467-9590.2009.00468.x | s2cid = 120663098 }} * {{cite journal | last1 = Wang | first1 = Yingqian | last2 = Zhang | first2 = Qijun | date = 2011 | title = Decomposing a planar graph with girth at least 8 into a forest and a matching | journal = Discrete Mathematics | volume = 311 | issue = 10–11 | pages = 844–849 | doi = 10.1016/j.disc.2011.01.019 | doi-access= free }} * {{cite journal | last1 = Montassier | first1 = Mickaël | last2 = Ossona de Mendez | first2 = Patrice | author2-link = Patrice Ossona de Mendez | last3 = André | first3 = Raspaud | last4 = Zhu | first4 = Xuding | date = 2012 | title = Decomposing a graph into forests | journal = Journal of Combinatorial Theory, Series B | volume = 102 | issue = 1 | pages = 38–52 | ref = {{harvid|Montassier et al.|2012}} | doi = 10.1016/j.jctb.2011.04.001 | doi-access= free }} {{refend}}
Category:Graph invariants Category:Graph theory objects