(a, b)-bontás

Egy irányítatlan gráf ( a , b )-felbontása az élek felosztása a + 1 halmazokra, amelyek mindegyike egy erdőt reprezentál , kivéve azt, amelyik legfeljebb b fokozatú . Ha ez a gráf egyben erdő is, akkor az ilyen dekompozíciót F( a , b )-dekompozíciónak nevezzük .

Egy a fa gráf ( a , 0)-felbontható. Bármilyen ( a , 0 )- vagy ( a , 1 )-felbontás F( a , 0 )-, illetve F( a , 1 )-bontás.

Grafikonosztályok

Bármely sík gráf F(2, 4)-felbontható [1]
Bármely sík gráf , amelynek kerülete legalább az $G$ $g$
- F(2, 0)-felbontható, ha
[2] $g\geqslant 4$
(1, 4) - felbontható, ha [3] . $g\geqslant 5$
F(1, 2) - felbontható, ha [4] . $g\geqslant 6$
F(1, 1)-felbontható, ha [5] , vagy ha bármely ciklus háromszög vagy legalább 8 élű ciklus, amely nem háromszögben van [6] $g\geqslant 8$ $G$
(1, 5) - felbontható, ha nincs 4 ciklusa [7] $G$

Bármely külső síkbeli gráf F(2, 0)-felbontható [2] és (1,3)-felbontható [8]

Jegyzetek

↑ Gonçalves, 2009 , Balogh, Kochol, Pluhár, Yu, 2005 hipotézise . Goncalves eredménye Nash-Williams ( Nash-Williams, 1964 ), majd Balogh, Kochol, Pluhár, Yu, 2005 eredményének javítása .
↑ 1 2 Nash-Williams ( Nash-Williams, 1964 ) eredményeiből következik.
↑ He, Hou, Lih, Shao et al., 2002 .
↑ Montassier, Ossona de Mendez, André és Zhu ( Montassier, Ossona de Mendez, André, Zhu, 2012 ) eredményeiből következik, melynek eredményét He, Hu, Li, Shao és társai javították ( He, Hou , Lih, Shao et al., 2002 ), majd Kleitman ( Kleitman, 2008 ).
↑ Wang és Zang bizonyította ( Wang, Zhang, 2011 ), és (függetlenül) Montassier, Ossona de Mendez, André és Zhu ( Montassier, Ossona de Mendez, André, Zhu, 2012 ) eredményeiből következik, amelyek javították a Chi-t, Hu, Li, Shao és munkatársai ( He, Hou, Lih, Shao és mtsai, 2002 ) a 11-es körmérethez, majd Bassa, Burns, Campbell és munkatársai ( Bassa, Burns, Campbell és mtsai, 2010 ) a kerülethez 10 és Borodin, Kostochka, Sheikh and Yu ( Borodin, Kostochka, Sheikh, Yu (a), 2008 ) a 9-es körmérethez.
↑ ( Borodin, Ivanova, Kostochka, Sheikh (b), 2009 ), bár ezt a cikk kifejezetten nem mondja ki.
↑ Borodin, Ivanova, Kostochka, Sheikh ( Borodin, Ivanova, Kostochka, Sheikh (a), 2009 ), aki javította Hee, Hu, Li, Shao és társai eredményét ( He, Hou, Lih, Shao et al., 2002 ), valamint az előző eredményt ( Borodin, Kostochka, Sheikh, Yu (b), 2008 ).
↑ Guan és Zhu bizonyította az eredmény kifejezett megjelölése nélkül ( Guan, Zhu, 1999 ).

Irodalom

Crispin St. John Alvah Nash-Williams. Véges gráfok bontása erdőkre // Journal of the London Mathematical Society . - 1964. - T. 39 , sz. 1 . - S. 12 . - doi : 10.1112/jlms/s1-39.1.12 .
Guan DJ, Zhu X. Outerplanar gráfok kromatikus száma játékban // Journal of Graph Theory. - 1999. - T. 30 , sz. 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. Síkgráfok él-partíciói és játék színezőszámai // Journal of Graph Theory. - 2002. - T. 41 . – S. 307–311 . - doi : 10.1002/jgt.10069 .
Balogh József, Martin Kochol, Pluhár András, Xingxing Yu. Síkgráfok lefedése erdőkkel // 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. Egy körív 6 síkgrafikon éleinek particionálása az erdő éleire és egy diszjunkt utak és ciklusok halmazára // Kézirat. – 2008.
Daniel Goncalves. Síkgráfok lefedése erdőkkel, egy határos maximális fok // 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 , sz. 3 . – S. 213–228 . doi : 10.1111 / j.1467-9590.2009.00468.x .
Yingqian Wang, Qijun Zhang. Legalább 8-as kerületű síkgráf felbontása erdőre és egy megfelelőre // Discrete Mathematics. - 2011. - T. 311 , sz. 10-11 . – S. 844–849 . - doi : 10.1016/j.disc.2011.01.019 .
Mickaël Montassier, Patrice Ossona de Mendez, Raspaud André, Xuding Zhu. Grafikon bontása erdőkre // Journal of Combinatorial Theory, Series B. - 2012. - Vol. 102 , no. 1 . – S. 38–52 . - doi : 10.1016/j.jctb.2011.04.001 .