(a, b)-разложение

(a, b)-разложение неориентированного графа — это разбиение рёбер на a + 1 множеств, каждое из которых представляет лес, за исключением одного, имеющего степень, не превосходящую b. Если этот граф тоже является лесом, такое разложение называется F(a, b)-разложением.

Граф с древесностью a является (a, 0)-разложимым. Любое (a, 0)-разложение или (a, 1)-разложение является a 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).

[_fa33b833bb9122cd-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]

(a, b)-разложение

Классы графов

Примечания

Литература

Похожие исследовательские статьи