( a , b )-rozkład

W teorii grafów rozkład ( a , b ) grafu nieskierowanego polega na podziale jego krawędzi na zbiory a + 1, z których każdy indukuje las, z wyjątkiem jednego, który indukuje graf o maksymalnym stopniu b . Jeśli ten graf jest również lasem, wtedy nazywamy to F( a , b ) .

00 Graf z arborycznością a jest ( a , 0)-rozkładalny. Każdy ( a , )-rozkład lub ( a , 1 )-rozkład jest odpowiednio F( a , )-rozkładem lub F( a , 1 )-rozkładem.

Klasy wykresów

• Każdy graf planarny jest F(2,4)-rozkładalny.
• Każdy wykres $obwodem$ z co najmniej $_$ równy
  • F (2, 0) -rozkładalny, jeśli ${\ Displaystyle g \ geq 4}$ .
  • (1, 4) -rozkładalny, jeśli ${\ Displaystyle g \ geq 5}$ .
  • F (1, 2) -rozkładalny, jeśli ${\ Displaystyle g \ geq 6}$ .
  • F (1, 1) -rozkładalny, jeśli $lub$ jeśli każdy cykl z $jest$ z co najmniej 8 krawędziami nie należącymi do trójkąta.
  • (1, 5) -rozkładalny, jeśli $.$ ma 4 cykli
• Każdy graf płaszczyzny zewnętrznej jest F(2, 0)-rozkładalny i (1,3)-rozkładalny.

Referencje (porządek chronologiczny)

•   Nash-Williams, Crispin St. John Alvah (1964). „Rozkład grafów skończonych na lasy”. Journal of London Mathematical Society . 39 (1): 12. doi : 10.1112/jlms/s1-39.1.12 . MR 0161333 .
• Guan, DJ; Zhu, Xuding (1999). „Gra chromatyczna liczba grafów zewnętrznych”. Dziennik teorii grafów . 30 (1): 67–70. doi : 10.1002/(sici)1097-0118(199901)30:1<67::aid-jgt7>3.0.co;2-m .
•   On, Wenjie; Hou, Xiaoling; Lih, Ko-Wei; Shao, Jiating; Wang, Weifan; Zhu, Xuding (2002). „Podziały krawędziowe grafów planarnych i ich numery do kolorowania gier”. Dziennik teorii grafów . 41 (4): 307–311. doi : 10.1002/jgt.10069 . S2CID 20929383 .
• Balogh, József; Kochał, Marcin; Pluhár, András; Yu, Xingxing (2005). „Pokrywanie grafów planarnych lasami” . Dziennik teorii kombinatorycznej, seria B. 94 (1): 147–158. doi : 10.1016/j.ejc.2007.06.020 .
• Borodin, Oleg W.; Kostochka, Aleksandr V.; Szejk, Naeem N.; Yu, Gexin (2008). „Rozkład płaskiego wykresu o obwodzie 9 na las i dopasowanie” . Europejski Dziennik Kombinatoryki . 29 (5): 1235–1241. doi : 10.1016/j.ejc.2007.06.020 .
•    Borodin, Oleg W.; Kostochka, Aleksandr V.; Szejk, Naeem N.; Yu, Gexin (2008). „ M -stopnie grafów planarnych wolnych od czworokątów” (PDF) . Dziennik teorii grafów . 60 (1): 80–85. CiteSeerX 10.1.1.224.8397 . doi : 10.1002/jgt.20346 . S2CID 7486622 .
• Kleitman, Daniel J. (2008). „Podział krawędzi wykresu płaskiego obwodu 6 na krawędzie lasu i zestawu rozłącznych ścieżek i cykli”. Rękopis .
• Gonçalves, Daniel (2009). „Pokrycie grafów planarnych lasami, z których jeden ma ograniczony stopień maksymalny” . Dziennik teorii kombinatorycznej, seria B. 99 (2): 314–322. doi : 10.1016/j.jctb.2008.07.004 .
•   Borodin, Oleg W.; Iwanowa, Anna O.; Kostochka, Aleksandr V.; Szejk, Naeem N. (2009). „Rozkłady grafów planarnych wolnych od czworokątów” (PDF) . Dyskusje Teoria grafów Mathematicae . 29 : 87–99. CiteSeerX 10.1.1.224.8787 . doi : 10.7151/dmgt.1434 .
• Borodin, Oleg W.; Iwanowa, Anna O.; Kostochka, Aleksandr V.; Szejk, Naeem N. (2009). „Wykresy planarne rozkładające się na las i dopasowanie” . Matematyka dyskretna . 309 (1): 277–279. doi : 10.1016/j.disc.2007.12.104 .
•   Bassa, A.; Burns, J.; Campbell, J.; Deshpande, A.; Farley, J.; Halsey, L.; Ho, S.-Y.; Kleitman D.; Michalakis, S.; Persson, PO; Pylyavskyy, P.; Rademacher, L.; Riehl, A.; Rios, M.; Samuel, J.; Tenner, BE; Vijayasarathy, A.; Zhao, L. (2010). „Podział planarnego wykresu obwodu 10 na las i dopasowanie”. Europejski Dziennik Kombinatoryki . 124 (3): 213–228. doi : 10.1111/j.1467-9590.2009.00468.x . S2CID 120663098 .
• Wang, Yingqian; Zhang, Qijun (2011). „Rozkład płaskiego wykresu o obwodzie co najmniej 8 na las i dopasowanie” . Matematyka dyskretna . 311 (10–11): 844–849. doi : 10.1016/j.disc.2011.01.019 .
• Montassier, Mickaël; Ossona de Mendez, Patrice ; Andrzej, Raspaud; Zhu, Xuding (2012). „Rozkład wykresu na lasy” . Dziennik teorii kombinatorycznej, seria B. 102 (1): 38–52. doi : 10.1016/j.jctb.2011.04.001 .