(a, b)-nedbrydning

En ( a , b )-nedbrydning af en urettet graf  er en opdeling af kanter i a + 1-sæt, som hver repræsenterer en skov , undtagen en, der højst har grad b . Hvis denne graf også er en skov, kaldes en sådan nedbrydning en F( a , b )-dekomponering .

En trægraf a er ( a , 0)-nedbrydelig. Enhver ( a , 0 )-nedbrydning eller ( a , 1 )-nedbrydning er henholdsvis en F( a , 0 )-nedbrydning eller F( a , 1 )-dekomponering.

Grafklasser

  • Enhver ydreplanær graf er F(2, 0)-nedbrydelig [2] og (1, 3)-nedbrydelig [8]

    • Noter

    1. ↑ Gonçalves, 2009 , hypotese af Balogh, Kochol, Pluhár, Yu, 2005 . Resultatet af Goncalves er en forbedring af resultatet af Nash-Williams ( Nash-Williams, 1964 ), derefter Balogh, Kochol, Pluhár, Yu, 2005 .
    2. ↑ 1 2 Følger fra resultater af Nash-Williams ( Nash-Williams, 1964 ).
    3. ↑ He, Hou, Lih, Shao et al., 2002 .
    4. ↑ Følger af resultaterne af Montassier, Ossona de Mendez, André og Zhu ( Montassier, Ossona de Mendez, André, Zhu, 2012 ), hvis resultat blev forbedret af He, Hu, Li, Shao et al. ( He, Hou) , Lih, Shao et al. ., 2002 ), derefter Kleitman ( Kleitman, 2008 ).
    5. ↑ Bevist af Wang og Zang ( Wang, Zhang, 2011 ) og (uafhængigt) følger af resultaterne af Montassier, Ossona de Mendez, André og Zhu ( Montassier, Ossona de Mendez, André, Zhu, 2012 ), som forbedrede Chi, Hu, Li, Shao et al. ( He, Hou, Lih, Shao et al., 2002 ) for omkreds 11, og derefter Bassa, Burns, Campbell et al. ( Bassa, Burns, Campbell et al., 2010 ) for omkreds 10 og Borodin, Kostochka, Sheikh og Yu ( Borodin, Kostochka, Sheikh, Yu (a), 2008 ) for omkreds 9.
    6. ↑ ( Borodin, Ivanova, Kostochka, Sheikh (b), 2009 ), selvom dette ikke er udtrykkeligt angivet i artiklen.
    7. ↑ Borodin, Ivanova, Kostochka, Sheikh ( Borodin, Ivanova, Kostochka, Sheikh (a), 2009 ), som forbedrede resultatet af Hee, Hu, Li, Shao et al. ( He, Hou, Lih, Shao et al., 2002 ), såvel som det tidligere resultat ( Borodin, Kostochka, Sheikh, Yu (b), 2008 ).
    8. ↑ Bevist af Guan og Zhu uden eksplicit angivelse af resultatet ( Guan, Zhu, 1999 ).

    Litteratur