(a, b)-розклад — Вікіпедія

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

Граф з деревністю a є (a, 0)-розкладаним. Будь-який (a, 0)-розклад або (a, 1)-розклад є F(a, 0)-розкладом або F(a, 1)-розкладом відповідно.

Класи графів

Будь-який планарний граф є F(2, 4)-розкладаним^[1]
Будь-який планарний граф $G$ $G$ з обхватом щонайменше $g$ $g$ є
- F(2, 0)-розкладаним, якщо $g\geqslant 4$ ^[2];
- (1, 4)-розкладаним, якщо $g\geqslant 5$ ^[3];
- F(1, 2)-розкладаним, якщо $g\geqslant 6$ ^[4];
- F(1, 1)-розкладаним, якщо $g\geqslant 8$ ^[5] або якщо будь-який цикл у $G$ є або трикутником, або циклом з мінімум 8 ребрами, що не належать трикутнику^[6];
- (1, 5)-розкладним, якщо $G$ не має 4-циклів^[7].
Будь-який зовніпланарний граф є F(2, 0)-розкладаним^[2] і (1, 3)-розкладаним^[8].

Примітки

↑ Gonçalves, 2009, гіпотезу висунули Балог, Кохол, Плугар і Ю (Balogh, Kochol, Pluhár, Yu, 2005). Результат Гонкалвеса покращує результат Неш-Вільямса (Nash-Williams, 1964), потім Балога, Кохола, Плугара і Ю (Balogh, Kochol, Pluhár, Yu, 2005).
↑ ^а ^б Випливає з результатів Неш-Вільямса (Nash-Williams, 1964).
↑ He, Hou, Lih, Shao та ін., 2002.
↑ Випливає з результатів Монтасьє, Оссони де Мендез, Андре та Зу (Montassier, Ossona de Mendez, André, Zhu, 2012), результат якого покращили Хі, Ху, Лі, Шао та ін. (He, Hou, Lih, Shao та ін., 2002), потім Кляйтман (Kleitman, 2008).
↑ Довели Ванг і Занг (Wang, Zhang, 2011) і (незалежно) випливає з результатів Монтасьє, Оссони де Мендез, Андре та Зу (Montassier, Ossona de Mendez, André, Zhu, 2012), які покращили Хі, Ху, Лі, Шао та ін. (He, Hou, Lih, Shao та ін., 2002) для обхвату 11, а потім Басса, Бернс, Кемпбелл та ін. (Bassa, Burns, Campbell та ін., 2010) для обхвату 10 і Бородін, Косточка, Шейх і Ю (Borodin, Kostochka, Sheikh, Yu (a), 2008) для обхвату 9.
↑ (Borodin, Ivanova, Kostochka, Sheikh (b), 2009), хоча це явно в статті й не стверджується.
↑ Бородін, Іванова, Косточка, Шейх (Borodin, Ivanova, Kostochka, Sheikh (a), 2009), які покращили результат Хі, Ху, Лі, Шао та ін. (He, Hou, Lih, Shao та ін., 2002), а також попередній результат (Borodin, Kostochka, Sheikh, Yu (b), 2008).
↑ Довели Гуан та Зу без явного вказання результату (Guan, Zhu, 1999).

Література

Crispin St. John Alvah Nash-Williams. Decomposition of finite graphs into forests // Journal of the London Mathematical Society. — 1964. — Т. 39, вип. 1. — С. 12. — DOI:10.1112/jlms/s1-39.1.12.
Guan D. J., Zhu X. Game chromatic number of outerplanar graphs // Journal of Graph Theory. — 1999. — Т. 30, вип. 1. — С. 67–70. — DOI:10.1002/(sici)1097-0118(199901)30:1<67::aid-jgt7>3.0.co;2-m.
Wenjie He, Xiaoling Hou, Ko-Wei Lih, Jiating Shao, Weifan Wang, Xuding Zhu. Edge-partitions of planar graphs and their game coloring numbers // Journal of Graph Theory. — 2002. — Т. 41. — С. 307–311. — DOI:10.1002/jgt.10069.
József Balogh, Martin Kochol, András Pluhár, Xingxing Yu. Covering planar graphs with forests // Journal of Combinatorial Theory, Series B. — 2005. — Т. 94, вип. 1. — С. 147–158. — DOI:10.1016/j.ejc.2007.06.020.
Oleg V. Borodin, Alexandr V. Kostochka, Naeem N. Sheikh, Gexin Yu. Decomposing a planar graph with girth 9 into a forest and a matching // European Journal of Combinatorics. — 2008. — Т. 29, вип. 5. — С. 1235–1241. — DOI:10.1016/j.ejc.2007.06.020.
Oleg V. Borodin, Alexandr V. Kostochka, Naeem N. Sheikh, Gexin Yu. M-Degrees of Quadrangle-Free Planar Graphs // Journal of Graph Theory. — 2008. — Т. 60, вип. 1. — С. 80–85. — DOI:10.1002/jgt.20346.
Daniel J. Kleitman. 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. — 2008.
Daniel Gonçalves. Covering planar graphs with forests, one having bounded maximum degree // Journal of Combinatorial Theory, Series B. — 2009. — Т. 99, вип. 2. — С. 314–322. — DOI:10.1016/j.jctb.2008.07.004.
Oleg V. Borodin, Anna O. Ivanova, Alexandr V. Kostochka, Naeem N. Sheikh. Decompositions of Quadrangle-Free Planar Graphs // Discussiones Mathematicae Graph Theory. — 2009. — Т. 29. — С. 87–99. — DOI:10.7151/dmgt.1434.
Oleg V. Borodin, Anna O. Ivanova, Alexandr V. Kostochka, Naeem N. Sheikh. Planar graphs decomposable into a forest and a matching // Discrete Mathematics. — 2009. — Т. 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. Partitioning a Planar Graph of Girth 10 into a Forest and a Matching // European Journal of Combinatorics. — 2010. — Т. 124, вип. 3. — С. 213–228. — DOI:10.1111/j.1467-9590.2009.00468.x.
Yingqian Wang, Qijun Zhang. Decomposing a planar graph with girth at least 8 into a forest and a matching // Discrete Mathematics. — 2011. — Т. 311, вип. 10—11. — С. 844–849. — DOI:10.1016/j.disc.2011.01.019.
Mickaël Montassier, Patrice Ossona de Mendez, Raspaud André, Xuding Zhu. Decomposing a graph into forests // Journal of Combinatorial Theory, Series B. — 2012. — Т. 102, вип. 1. — С. 38–52. — DOI:10.1016/j.jctb.2011.04.001.

[1] Gonçalves, 2009, гіпотезу висунули Балог, Кохол, Плугар і Ю (Balogh, Kochol, Pluhár, Yu, 2005). Результат Гонкалвеса покращує результат Неш-Вільямса (Nash-Williams, 1964), потім Балога, Кохола, Плугара і Ю (Balogh, Kochol, Pluhár, Yu, 2005).

[NW-2] а ^б Випливає з результатів Неш-Вільямса (Nash-Williams, 1964).

[FOOTNOTEHe,_Hou,_Lih,_Shao_та_ін.2002-3] He, Hou, Lih, Shao та ін., 2002.

[4] Випливає з результатів Монтасьє, Оссони де Мендез, Андре та Зу (Montassier, Ossona de Mendez, André, Zhu, 2012), результат якого покращили Хі, Ху, Лі, Шао та ін. (He, Hou, Lih, Shao та ін., 2002), потім Кляйтман (Kleitman, 2008).

[5] Довели Ванг і Занг (Wang, Zhang, 2011) і (незалежно) випливає з результатів Монтасьє, Оссони де Мендез, Андре та Зу (Montassier, Ossona de Mendez, André, Zhu, 2012), які покращили Хі, Ху, Лі, Шао та ін. (He, Hou, Lih, Shao та ін., 2002) для обхвату 11, а потім Басса, Бернс, Кемпбелл та ін. (Bassa, Burns, Campbell та ін., 2010) для обхвату 10 і Бородін, Косточка, Шейх і Ю (Borodin, Kostochka, Sheikh, Yu (a), 2008) для обхвату 9.

[6] (Borodin, Ivanova, Kostochka, Sheikh (b), 2009), хоча це явно в статті й не стверджується.

[7] Бородін, Іванова, Косточка, Шейх (Borodin, Ivanova, Kostochka, Sheikh (a), 2009), які покращили результат Хі, Ху, Лі, Шао та ін. (He, Hou, Lih, Shao та ін., 2002), а також попередній результат (Borodin, Kostochka, Sheikh, Yu (b), 2008).

[8] Довели Гуан та Зу без явного вказання результату (Guan, Zhu, 1999).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]