Перегляд вихідного коду сторінки (a, b)-розклад

'''(''a'',&nbsp;''b'')-Розклад''' неорієнтованого [[Теорія графів|графа]]&nbsp;— це розбиття ребер на ''a'''''&nbsp;'''+'''&nbsp;'''1 множин, кожна з яких представляє [[Дерево (теорія графів)|ліс]], за винятком однієї, степінь якої не перевищує ''b''. Якщо цей граф теж є лісом, такий розклад називають '''F(''a'',&nbsp;''b'')-розкладом'''.

Граф з [[Деревність графа|деревністю]] ''a'' є (''a'','''&nbsp;'''0)-розкладаним. Будь-який (''a'','''&nbsp;'''''0'')-розклад або (''a'','''&nbsp;'''''1'')-розклад є F(''a'','''&nbsp;'''''0'')-розкладом або F(''a'','''&nbsp;'''''1'')-розкладом відповідно.

== Класи графів ==

* Будь-який [[планарний граф]] є F(2,'''&nbsp;'''4)-розкладаним<ref>{{Sfn0|Gonçalves|2009}}, гіпотезу висунули Балог, Кохол, Плугар і Ю ({{Sfn0|Balogh, Kochol, Pluhár, Yu|2005}}). Результат Гонкалвеса покращує результат Неш-Вільямса ({{Sfn0|Nash-Williams|1964}}), потім Балога, Кохола, Плугара і Ю ({{Sfn0|Balogh, Kochol, Pluhár, Yu|2005}}).</ref>
* Будь-який [[планарний граф]] <math>G</math> з [[Обхват (теорія графів)|обхватом]] щонайменше <math>g</math> є
** F(2,'''&nbsp;'''0)-розкладаним, якщо <math>g \geqslant 4</math><ref name="NW">Випливає з результатів Неш-Вільямса ({{Sfn0|Nash-Williams|1964}}).</ref>;
** (1,'''&nbsp;'''4)-розкладаним, якщо <math>g \geqslant 5</math>{{Sfn|He, Hou, Lih, Shao та ін.|2002}};
** F(1,'''&nbsp;'''2)-розкладаним, якщо <math>g \geqslant 6</math><ref>Випливає з результатів Монтасьє, Оссони де Мендез, Андре та Зу ({{Sfn0|Montassier, Ossona de Mendez, André, Zhu|2012}}), результат якого покращили Хі, Ху, Лі, Шао та ін. ({{Sfn0|He, Hou, Lih, Shao та ін.|2002}}), потім Кляйтман ({{Sfn0|Kleitman|2008}}).</ref>;
** F(1,'''&nbsp;'''1)-розкладаним, якщо <math>g \geqslant 8</math><ref>Довели Ванг і Занг ({{Sfn0|Wang, Zhang|2011}}) і (незалежно) випливає з результатів Монтасьє, Оссони де Мендез, Андре та Зу ({{Sfn0|Montassier, Ossona de Mendez, André, Zhu|2012}}), які покращили Хі, Ху, Лі, Шао та ін. ({{Sfn0|He, Hou, Lih, Shao та ін.|2002}}) для обхвату 11, а потім Басса, Бернс, Кемпбелл та ін. ({{Sfn0|Bassa, Burns, Campbell та ін.|2010}}) для обхвату 10 і Бородін, Косточка, Шейх і Ю ({{Sfn0|Borodin, Kostochka, Sheikh, Yu (a)|2008}}) для обхвату 9.</ref> або якщо будь-який цикл у <math>G</math> є або трикутником, або циклом з мінімум 8 ребрами, що не належать трикутнику<ref>({{Sfn0|Borodin, Ivanova, Kostochka, Sheikh (b)|2009}}), хоча це явно в статті й не стверджується.</ref>;
** (1,'''&nbsp;'''5)-розкладним, якщо <math>G</math> не має 4-циклів<ref>Бородін, Іванова, Косточка, Шейх ({{Sfn0|Borodin, Ivanova, Kostochka, Sheikh (a)|2009}}), які покращили результат Хі, Ху, Лі, Шао та ін. ({{Sfn0|He, Hou, Lih, Shao та ін.|2002}}), а також попередній результат ({{Sfn0|Borodin, Kostochka, Sheikh, Yu (b)|2008}}).</ref>.
* Будь-який [[зовніпланарний граф]] є F(2,'''&nbsp;'''0)-розкладаним<ref name="NW" /> і (1,'''&nbsp;'''3)-розкладаним<ref>Довели Гуан та Зу без явного вказання результату ({{Sfn0|Guan, Zhu|1999}}).</ref>.

== Примітки ==
{{примітки|2}}

== Література ==
* {{Стаття|author=Crispin St. John Alvah Nash-Williams|ref=Nash-Williams|title=Decomposition of finite graphs into forests|видання=[[Journal of the London Mathematical Society]]|том=39|issue=1|рік=1964|pages=12|doi=10.1112/jlms/s1-39.1.12}}
* {{Стаття|author=Guan D. J., Zhu X.|ref=Guan, Zhu|рік=1999|title=Game chromatic number of outerplanar graphs|url=http://onlinelibrary.wiley.com/doi/10.1002/%28SICI%291097-0118%28199901%2930:1%3C67::AID-JGT7%3E3.0.CO;2-M/abstract|видання=Journal of Graph Theory|том=30|issue=1|pages=67–70|doi=10.1002/(sici)1097-0118(199901)30:1<67::aid-jgt7>3.0.co;2-m}}
* {{Стаття|author=Wenjie He, Xiaoling Hou, Ko-Wei Lih, Jiating Shao, Weifan Wang, Xuding Zhu|ref=He, Hou, Lih, Shao та ін.|рік=2002|title=Edge-partitions of planar graphs and their game coloring numbers|url=http://onlinelibrary.wiley.com/doi/10.1002/jgt.10069/abstract|видання=Journal of Graph Theory|том=41|pages=307–311|doi=10.1002/jgt.10069}}
* {{Стаття|ref=Balogh, Kochol, Pluhár, Yu|author=József Balogh, Martin Kochol, András Pluhár, Xingxing Yu|рік=2005|title=Covering planar graphs with forests|url=http://www.sciencedirect.com/science/article/pii/S0095895604001273|видання=Journal of Combinatorial Theory, Series B|том=94|issue=1|pages=147–158|doi=10.1016/j.ejc.2007.06.020}}
* {{Стаття|ref=Borodin, Kostochka, Sheikh, Yu (a)|author=Oleg V. Borodin, Alexandr V. Kostochka, Naeem N. Sheikh, Gexin Yu|рік=2008|title=Decomposing a planar graph with girth 9 into a forest and a matching|url=http://www.sciencedirect.com/science/article/pii/S0195669807001151|видання=European Journal of Combinatorics|том=29|issue=5|pages=1235–1241|doi=10.1016/j.ejc.2007.06.020}}
* {{Стаття|ref=Borodin, Kostochka, Sheikh, Yu (b)|author=Oleg V. Borodin, Alexandr V. Kostochka, Naeem N. Sheikh, Gexin Yu|рік=2008|title=''M''-Degrees of Quadrangle-Free Planar Graphs|url=http://www.math.uiuc.edu/~kostochk/docs/2012/jgt09bsy.pdf|видання=Journal of Graph Theory|том=60|issue=1|pages=80–85|doi=10.1002/jgt.20346}}
* {{Стаття|author=Daniel J. Kleitman|ref=Kleitman|рік=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|видання=Manuscript}}
* {{Стаття|author=Daniel Gonçalves|ref=Gonçalves|рік=2009|title=Covering planar graphs with forests, one having bounded maximum degree|url=http://www.sciencedirect.com/science/article/pii/S0095895608000774|видання=Journal of Combinatorial Theory, Series B|том=99|issue=2|pages=314–322|doi=10.1016/j.jctb.2008.07.004}}
* {{Стаття|ref=Borodin, Ivanova, Kostochka, Sheikh (a)|author=Oleg V. Borodin, Anna O. Ivanova, Alexandr V. Kostochka, Naeem N. Sheikh|рік=2009|title=Decompositions of Quadrangle-Free Planar Graphs|url=http://www.math.uiuc.edu/~kostochk/docs/2012/dmgt09bis.pdf|видання=Discussiones Mathematicae Graph Theory|том=29|pages=87–99|doi=10.7151/dmgt.1434}}
* {{Стаття|ref=Borodin, Ivanova, Kostochka, Sheikh (b)|author=Oleg V. Borodin, Anna O. Ivanova, Alexandr V. Kostochka, Naeem N. Sheikh|рік=2009|title=Planar graphs decomposable into a forest and a matching|url=http://www.sciencedirect.com/science/article/pii/S0012365X07010771|видання=Discrete Mathematics|том=309|issue=1|pages=277–279|doi=10.1016/j.disc.2007.12.104}}
* {{Стаття|ref=Bassa, Burns, Campbell и др.|author=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|title=Partitioning a Planar Graph of Girth 10 into a Forest and a Matching|url=http://onlinelibrary.wiley.com/doi/10.1111/j.1467-9590.2009.00468.x/abstract|видання=European Journal of Combinatorics|том=124|issue=3|pages=213–228|doi=10.1111/j.1467-9590.2009.00468.x}}
* {{Стаття|ref=Wang, Zhang|author=Yingqian Wang, Qijun Zhang|рік=2011|title=Decomposing a planar graph with girth at least 8 into a forest and a matching|url=http://www.sciencedirect.com/science/article/pii/S0012365X1100029X|видання=Discrete Mathematics|том=311|issue=10—11|pages=844–849|doi=10.1016/j.disc.2011.01.019}}
* {{Стаття|author=Mickaël Montassier, Patrice Ossona de Mendez, Raspaud André, Xuding Zhu|ref=Montassier, Ossona de Mendez, André, Zhu|рік=2012|title=Decomposing a graph into forests|url=http://www.sciencedirect.com/science/article/pii/S0095895611000438|видання=Journal of Combinatorial Theory, Series B|том=102|issue=1|pages=38–52|doi=10.1016/j.jctb.2011.04.001}}

[[Категорія:Об'єкти теорії графів]]
[[Категорія:Інваріанти графа]]