(a, b)-sönderdelning

En ( a , b )-nedbrytning av en oriktad graf är en uppdelning av kanter i a + 1 uppsättningar, som var och en representerar en skog , förutom en som har grad b . Om denna graf också är en skog kallas en sådan nedbrytning en F( a , b )-nedbrytning .

En trädgraf a är ( a , 0)-nedbrytbar. Varje ( a , 0 )-sönderdelning eller ( a , 1 )-sönderdelning är en F( a , 0 )-sönderdelning respektive F( a , 1 )-sönderdelning.

Grafklasser

Alla plana grafer är F(2, 4)-nedbrytbara [1]
Varje plan graf med omkrets åtminstone är $G$ $g$
- F(2, 0)-nedbrytbar om
[2] $g\geqslant 4$
(1, 4) - nedbrytbar om [3] . $g\geqslant 5$
F(1, 2) - nedbrytbar om [4] . $g\geqslant 6$
F(1, 1)-nedbrytbar om [5] eller om någon cykel är antingen en triangel eller en cykel med minst 8 kanter som inte är i en triangel [6] $g\geqslant 8$ $G$
(1, 5) - nedbrytbar om den inte har 4-cykler [7] $G$

Varje ytterplanär graf är F(2, 0)-nedbrytbar [2] och (1, 3)-nedbrytbar [8]

Anteckningar

↑ Gonçalves, 2009 , hypotes av Balogh, Kochol, Pluhár, Yu, 2005 . Resultatet av Goncalves är en förbättring av resultatet av Nash-Williams ( Nash-Williams, 1964 ), sedan Balogh, Kochol, Pluhár, Yu, 2005 .
↑ 1 2 Följer från resultat av Nash-Williams ( Nash-Williams, 1964 ).
↑ He, Hou, Lih, Shao et al., 2002 .
↑ Följer från resultaten av Montassier, Ossona de Mendez, André och Zhu ( Montassier, Ossona de Mendez, André, Zhu, 2012 ), vars resultat förbättrades av He, Hu, Li, Shao et al. ( He, Hou , Lih, Shao et al. ., 2002 ), sedan Kleitman ( Kleitman, 2008 ).
↑ Bevisat av Wang och Zang ( Wang, Zhang, 2011 ) och (oberoende) följer av resultaten av Montassier, Ossona de Mendez, André och Zhu ( Montassier, Ossona de Mendez, André, Zhu, 2012 ), som förbättrade Chi, Hu, Li, Shao et al. ( He, Hou, Lih, Shao et al., 2002 ) för omkrets 11, och sedan Bassa, Burns, Campbell et al. ( Bassa, Burns, Campbell et al., 2010 ) för omkrets 10 och Borodin, Kostochka, Sheikh och Yu ( Borodin, Kostochka, Sheikh, Yu (a), 2008 ) för omkrets 9.
↑ ( Borodin, Ivanova, Kostochka, Sheikh (b), 2009 ), även om detta inte uttryckligen anges i artikeln.
↑ Borodin, Ivanova, Kostochka, Sheikh ( Borodin, Ivanova, Kostochka, Sheikh (a), 2009 ), som förbättrade resultatet av Hee, Hu, Li, Shao et al. ( He, Hou, Lih, Shao et al., 2002 ), såväl som det tidigare resultatet ( Borodin, Kostochka, Sheikh, Yu (b), 2008 ).
↑ Bevisat av Guan och Zhu utan uttrycklig indikation på resultatet ( Guan, Zhu, 1999 ).

Litteratur

Crispin St. John Alvah Nash-Williams. Nedbrytning av finita grafer till skogar // Journal of the London Mathematical Society . - 1964. - T. 39 , nr. 1 . - S. 12 . - doi : 10.1112/jlms/s1-39.1.12 .
Guan DJ, Zhu X. Spelkromatiska antal ytterplanära grafer // Journal of Graph Theory. - 1999. - T. 30 , nr. 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. Kantpartitioner av plana grafer och deras spelfärgsnummer // 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. Täcker plana grafer med skogar // Journal of Combinatorial Theory, Series B. - 2005. - V. 94 , nr. 1 . — S. 147–158 . - doi : 10.1016/j.ejc.2007.06.020 .
Daniel J. Kleitman. Dela in kanterna på en omkrets 6 Planar Graph i de av en skog och de av en uppsättning disjunkta banor och cykler // Manuskript. — 2008.
Daniel Goncalves. Täcker plana grafer med skogar, en som har avgränsad maximal grad // Journal of Combinatorial Theory, Series B. - 2009. - Vol. 99 , nr. 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 , nr. 3 . — S. 213–228 . doi : 10.1111 / j.1467-9590.2009.00468.x .
Yingqian Wang, Qijun Zhang. Nedbrytning av en plan graf med omkrets minst 8 i en skog och en matchande // Diskret matematik. - 2011. - T. 311 , nr. 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 , nr. 1 . — S. 38–52 . - doi : 10.1016/j.jctb.2011.04.001 .