(a, b)-hajoaminen

Suuntaamattoman graafin ( a , b )-hajotelma on reunojen osio a + 1 -joukkoon, joista jokainen edustaa metsää , paitsi yksi, jonka aste on korkeintaan b . Jos tämä graafi on myös metsä, tällaista hajotusta kutsutaan F( a , b ) -hajotukseksi .

Puukaavio a on ( a , 0)-hajottava . Mikä tahansa ( a , 0 )- tai ( a , 1 )-hajoaminen on F( a , 0 )-hajotus tai vastaavasti F( a , 1 )-hajoaminen.

Kaavioluokat

Mikä tahansa tasograafi on F(2, 4)-hajottava [1]
Mikä tahansa tasograafi , jossa on vähintään ympärysmitta , on $G$ $g$
- F(2, 0)-hajoava, jos
[2] $g\geqslant 4$
(1, 4) - hajoava, jos [3] . $g\geqslant 5$
F(1, 2) - hajoava, jos [4] . $g\geqslant 6$
F(1, 1)-hajottava, jos [5] tai jos jokin sykli on joko kolmio tai sykli, jossa on vähintään 8 reunaa, jotka eivät ole kolmiossa [6] $g\geqslant 8$ $G$
(1, 5) - hajoava, jos siinä ei ole 4-jaksoa [7] $G$

Mikä tahansa ulompi tasograafi on F(2, 0)-hajottava [2] ja (1, 3)-hajottava [8]

Muistiinpanot

↑ Gonçalves, 2009 , hypoteesi Balogh, Kochol, Pluhár, Yu, 2005 . Goncalvesin tulos on parannus Nash-Williamsin ( Nash-Williams, 1964 ), sitten Balogh, Kochol, Pluhár, Yu, 2005 tulokseen .
↑ 1 2 Seuraa Nash-Williamsin ( Nash-Williams, 1964 ) tuloksista.
↑ He, Hou, Lih, Shao et ai., 2002 .
↑ Seuraa Montassier, Ossona de Mendez, André ja Zhu ( Montassier, Ossona de Mendez, André, Zhu, 2012 ) tuloksista, joiden tulosta paransivat He, Hu, Li, Shao ym. ( He, Hou , Lih, Shao et ai., 2002 ), sitten Kleitman ( Kleitman, 2008 ).
↑ Wangin ja Zangin todentama ( Wang, Zhang, 2011 ) ja (riippumattomasti) seuraa Montassier, Ossona de Mendez, André ja Zhu ( Montassier, Ossona de Mendez, André, Zhu, 2012 ) tuloksista, jotka paransivat Chi:tä, Hu, Li, Shao ym. ( He, Hou, Lih, Shao et al., 2002 ) ympärysmitta 11, ja sitten Bassa, Burns, Campbell ym. ( Bassa, Burns, Campbell et al., 2010 ) 10 ja Borodin, Kostochka, Sheikh ja Yu ( Borodin, Kostochka, Sheikh, Yu (a), 2008 ) ympärysmitta 9.
↑ ( Borodin, Ivanova, Kostochka, Sheikh (b), 2009 ), vaikka tätä ei ole nimenomaisesti sanottu artikkelissa.
↑ Borodin, Ivanova, Kostochka, Sheikh ( Borodin, Ivanova, Kostochka, Sheikh (a), 2009 ), joka paransi Hee, Hu, Li, Shao ym. tulosta ( He, Hou, Lih, Shao et al., 2002 ), sekä edellinen tulos ( Borodin, Kostochka, Sheikh, Yu (b), 2008 ).
↑ Todistivat Guan ja Zhu ilman selkeää viittausta tulokseen ( Guan, Zhu, 1999 ).

Kirjallisuus

Crispin St. John Alvah Nash-Williams. Äärillisten graafien hajoaminen metsiin // Journal of the London Mathematical Society . - 1964. - T. 39 , no. 1 . - S. 12 . - doi : 10.1112/jlms/s1-39.1.12 .
Guan DJ, Zhu X. Outerplanar graphs -pelin kromaattinen lukumäärä // 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. Tasokaavioiden reuna-osioita ja niiden pelin väritysnumeroita // 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. Tasograafien peittäminen metsillä // 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. Ympyrän 6 tasokaavion reunojen osiointi metsän reunoihin ja epäyhtenäisten polkujen ja syklien joukon reunoihin // Käsikirjoitus. – 2008.
Daniel Goncalves. Tasograafien peittäminen metsillä, joilla on rajattu maksimiaste // 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. Tasomaisen ympäryskuvaajan 10 jakaminen metsään ja vastaavaan // European Journal of Combinatorics. - 2010. - T. 124 , no. 3 . — S. 213–228 . doi : 10.1111 / j.1467-9590.2009.00468.x .
Yingqian Wang, Qijun Zhang. Tasograafin, jonka ympärysmitta on vähintään 8, hajottaminen metsäksi ja vastaavaksi // Diskreetti matematiikka. - 2011. - T. 311 , no. 10-11 . — S. 844–849 . - doi : 10.1016/j.disc.2011.01.019 .
Mickaël Montassier, Patrice Ossona de Mendez, Raspaud André, Xuding Zhu. Kuvaajan hajottaminen metsiksi // Journal of Combinatorial Theory, Series B. - 2012. - Vol. 102 , no. 1 . - S. 38-52 . - doi : 10.1016/j.jctb.2011.04.001 .