(a, b) - rozklad

( a , b )-dekompozice neorientovaného grafu je rozdělení hran na množiny a + 1, z nichž každá představuje les , kromě jedné, která má stupeň nejvýše b . Pokud je tento graf také les, nazývá se takový rozklad F( a , b )-rozklad .

Stromový graf a je ( a , 0)-rozložitelný. Jakýkoli ( a , 0 )-rozklad nebo ( a , 1 )-rozklad je F( a , 0 )-rozklad nebo F( a , 1 )-rozklad.

Grafové třídy

Jakýkoli rovinný graf je F(2, 4)-rozložitelný [1]
Jakýkoli rovinný graf s obvodem alespoň je $G$ $G$
- F(2, 0)-rozložitelné, pokud
[2] $g\geqslant 4$
(1, 4) - rozložitelné, pokud [3] . $g\geqslant 5$
F(1, 2) - rozložitelné, pokud [4] . $g\geqslant 6$
F(1, 1)-rozložitelné, pokud [5] nebo je-li kterýkoli cyklus buď trojúhelník, nebo cyklus s alespoň 8 hranami, které nejsou v trojúhelníku [6] $g\geqslant 8$ $G$
(1, 5) - rozložitelné, pokud nemá 4 cykly [7] $G$

Jakýkoli vnější rovinný graf je F(2, 0)-rozložitelný [2] a (1, 3)-rozložitelný [8]

Poznámky

↑ Gonçalves, 2009 , předpokládali Balogh, Kochol, Pluhár, Yu, 2005 . Výsledkem Goncalvese je zlepšení výsledku Nash-Williamse ( Nash-Williams, 1964 ), dále Balogh, Kochol, Pluhár, Yu, 2005 .
↑ 1 2 Vyplývá z výsledků Nash-Williamse ( Nash-Williams, 1964 ).
↑ He, Hou, Lih, Shao a kol., 2002 .
↑ Vyplývá z výsledků Montassier, Ossona de Mendez, André a Zhu ( Montassier, Ossona de Mendez, André, Zhu, 2012 ), jejichž výsledek zlepšili He, Hu, Li, Shao aj. ( He, Hou , Lih, Shao a kol., 2002 ), poté Kleitman ( Kleitman, 2008 ).
↑ Ověřeno Wangem a Zangem ( Wang, Zhang, 2011 ) a (nezávisle) vyplývá z výsledků Montassier, Ossona de Mendez, André a Zhu ( Montassier, Ossona de Mendez, André, Zhu, 2012 ), které zlepšily Chi, Hu, Li, Shao a kol. ( He, Hou, Lih, Shao a kol., 2002 ) pro obvod 11 a poté Bassa, Burns, Campbell a kol. ( Bassa, Burns, Campbell a kol., 2010 ) pro obvod 10 a Borodin, Kostochka, Sheikh a Yu ( Borodin, Kostochka, Sheikh, Yu (a), 2008 ) pro obvod 9.
↑ ( Borodin, Ivanova, Kostochka, Sheikh (b), 2009 ), i když to není v článku výslovně uvedeno.
↑ Borodin, Ivanova, Kostochka, Sheikh ( Borodin, Ivanova, Kostochka, Sheikh (a), 2009 ), kteří zlepšili výsledek Hee, Hu, Li, Shao et al. ( He, Hou, Lih, Shao et al., 2002 ), stejně jako předchozí výsledek ( Borodin, Kostochka, Sheikh, Yu (b), 2008 ).
↑ Prokázali Guan a Zhu bez explicitního uvedení výsledku ( Guan, Zhu, 1999 ).

Literatura

Crispin St. John Alvah Nash-Williams. Dekompozice konečných grafů do lesů // Journal of the London Mathematical Society . - 1964. - T. 39 , čís. 1 . - S. 12 . - doi : 10.1112/jlms/s1-39.1.12 .
Guan DJ, Zhu X. Herní chromatický počet vnějších rovinných grafů // Journal of Graph Theory. - 1999. - T. 30 , no. 1 . — S. 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. Hranové oddíly rovinných grafů a jejich herní barvicí čísla // Journal of Graph Theory. - 2002. - T. 41 . — S. 307–311 . - doi : 10.1002/jgt.10069 .
József Balogh, Martin Kochol, András Pluhár, Xingxing Yu. Krytí planárních grafů lesy // Journal of Combinatorial Theory, Series B. - 2005. - V. 94 , no. 1 . — S. 147–158 . - doi : 10.1016/j.ejc.2007.06.020 .
Daniel J. Kleitman. Rozdělení okrajů obvodu 6 na rovinný graf na okraje lesa a na okraje sady nesouvislých cest a cyklů // Rukopis. — 2008.
Daniel Goncalves. Pokrývající rovinné grafy s lesy, z nichž jeden má omezený maximální stupeň // Journal of Combinatorial Theory, Series B. - 2009. - Vol.99 , no. 2 . — S. 314–322 . - doi : 10.1016/j.jctb.2008.07.004 .
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 BE, Vijayasarathy A., Zhao L. Partitioning a Planar Graph of Girth 10 into a Forest and a Matching // European Journal of Combinatorics. - 2010. - T. 124 , č. 3 . — S. 213–228 . doi : 10.1111 / j.1467-9590.2009.00468.x .
Yingqian Wang, Qijun Zhang. Rozložení rovinného grafu s obvodem alespoň 8 na les a odpovídající // diskrétní matematiku. - 2011. - T. 311 , č.p. 10-11 . — S. 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. - Vol. 102 , no. 1 . — S. 38–52 . - doi : 10.1016/j.jctb.2011.04.001 .