(a, b)-Розклад неорієнтованого графа — це розбиття ребер на a + 1 множин, кожна з яких представляє ліс, за винятком однієї, степінь якої не перевищує b. Якщо цей граф теж є лісом, такий розклад називають F(a, b)-розкладом.
Граф з деревністю a є (a, 0)-розкладаним. Будь-який (a, 0)-розклад або (a, 1)-розклад є F(a, 0)-розкладом або F(a, 1)-розкладом відповідно.
Класи графів
- Будь-який планарний граф є F(2, 4)-розкладаним
- Будь-який планарний граф з обхватом щонайменше є
- F(2, 0)-розкладаним, якщо ;
- (1, 4)-розкладаним, якщо ;
- F(1, 2)-розкладаним, якщо ;
- F(1, 1)-розкладаним, якщо або якщо будь-який цикл у є або трикутником, або циклом з мінімум 8 ребрами, що не належать трикутнику;
- (1, 5)-розкладним, якщо не має 4-циклів.
- Будь-який зовніпланарний граф є F(2, 0)-розкладаним і (1, 3)-розкладаним.
Примітки
- 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: .
- Guan D. J., Zhu X. Game chromatic number of outerplanar graphs // Journal of Graph Theory. — 1999. — Т. 30, вип. 1. — С. 67–70. — DOI: .
- 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: .
- 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: .
- 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: .
- 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: .
- 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: .
- 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: .
- 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: .
- 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: .
- 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: .
- 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: .
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
a b Rozklad neoriyentovanogo grafa ce rozbittya reber na a 1 mnozhin kozhna z yakih predstavlyaye lis za vinyatkom odniyeyi stepin yakoyi ne perevishuye b Yaksho cej graf tezh ye lisom takij rozklad nazivayut F a b rozkladom Graf z derevnistyu a ye a 0 rozkladanim Bud yakij a 0 rozklad abo a 1 rozklad ye F a 0 rozkladom abo F a 1 rozkladom vidpovidno Klasi grafivBud yakij planarnij graf ye F 2 4 rozkladanim Bud yakij planarnij graf G displaystyle G z obhvatom shonajmenshe g displaystyle g ye F 2 0 rozkladanim yaksho g 4 displaystyle g geqslant 4 1 4 rozkladanim yaksho g 5 displaystyle g geqslant 5 F 1 2 rozkladanim yaksho g 6 displaystyle g geqslant 6 F 1 1 rozkladanim yaksho g 8 displaystyle g geqslant 8 abo yaksho bud yakij cikl u G displaystyle G ye abo trikutnikom abo ciklom z minimum 8 rebrami sho ne nalezhat trikutniku 1 5 rozkladnim yaksho G displaystyle G ne maye 4 cikliv Bud yakij zovniplanarnij graf ye F 2 0 rozkladanim i 1 3 rozkladanim PrimitkiGoncalves 2009 gipotezu visunuli Balog Kohol Plugar i Yu Balogh Kochol Pluhar Yu 2005 Rezultat Gonkalvesa pokrashuye rezultat Nesh Vilyamsa Nash Williams 1964 potim Baloga Kohola Plugara i Yu Balogh Kochol Pluhar Yu 2005 Viplivaye z rezultativ Nesh Vilyamsa Nash Williams 1964 He Hou Lih Shao ta in 2002 Viplivaye z rezultativ Montasye Ossoni de Mendez Andre ta Zu Montassier Ossona de Mendez Andre Zhu 2012 rezultat yakogo pokrashili Hi Hu Li Shao ta in He Hou Lih Shao ta in 2002 potim Klyajtman Kleitman 2008 Doveli Vang i Zang Wang Zhang 2011 i nezalezhno viplivaye z rezultativ Montasye Ossoni de Mendez Andre ta Zu Montassier Ossona de Mendez Andre Zhu 2012 yaki pokrashili Hi Hu Li Shao ta in He Hou Lih Shao ta in 2002 dlya obhvatu 11 a potim Bassa Berns Kempbell ta in Bassa Burns Campbell ta in 2010 dlya obhvatu 10 i Borodin Kostochka Shejh i Yu Borodin Kostochka Sheikh Yu a 2008 dlya obhvatu 9 Borodin Ivanova Kostochka Sheikh b 2009 hocha ce yavno v statti j ne stverdzhuyetsya Borodin Ivanova Kostochka Shejh Borodin Ivanova Kostochka Sheikh a 2009 yaki pokrashili rezultat Hi Hu Li Shao ta in He Hou Lih Shao ta in 2002 a takozh poperednij rezultat Borodin Kostochka Sheikh Yu b 2008 Doveli Guan ta Zu bez yavnogo vkazannya rezultatu Guan Zhu 1999 LiteraturaCrispin St John Alvah Nash Williams Decomposition of finite graphs into forests Journal of the London Mathematical Society 1964 T 39 vip 1 S 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 T 30 vip 1 S 67 70 DOI 10 1002 sici 1097 0118 199901 30 1 lt 67 aid jgt7 gt 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 T 41 S 307 311 DOI 10 1002 jgt 10069 Jozsef Balogh Martin Kochol Andras Pluhar Xingxing Yu Covering planar graphs with forests Journal of Combinatorial Theory Series B 2005 T 94 vip 1 S 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 T 29 vip 5 S 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 T 60 vip 1 S 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 Goncalves Covering planar graphs with forests one having bounded maximum degree Journal of Combinatorial Theory Series B 2009 T 99 vip 2 S 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 T 29 S 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 T 309 vip 1 S 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 T 124 vip 3 S 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 T 311 vip 10 11 S 844 849 DOI 10 1016 j disc 2011 01 019 Mickael Montassier Patrice Ossona de Mendez Raspaud Andre Xuding Zhu Decomposing a graph into forests Journal of Combinatorial Theory Series B 2012 T 102 vip 1 S 38 52 DOI 10 1016 j jctb 2011 04 001