A matematika, azon belül a gráfelmélet területén egy irányítatlan gráf (a, b)-felbontása vagy (a, b)-dekompozíciója a gráf éleinek a + 1 halmazra való felbontása oly módon, hogy közülük a darab egy-egy erdőt feszít ki, a maradék pedig egy b maximális fokszámú gráfot. Ha a maradék gráf is erdő, F(a, b)-felbontásról beszélünk.
Egy a arboricitású gráf (a, 0)-felbontható. Minden (a, 0)-felbontásra, illetve (a, 1)-felbontásra igaz, hogy egyben F(a, 0)-felbontás, illetve F(a, 1)-felbontás.
Gráfosztályok
Minden síkbarajzolható gráf F(2, 4)-felbontható., megsejtője . eredményeit fejlesztette tovább. Minden síkbarajzolható gráf, melynek girthparamétere legalább : F(2, 0)-felbontható, ha . -ből következik. (1, 4)-felbontható, ha . F(1, 2)-felbontható, ha .-ből következik, , majd eredményeit továbbfejlesztve. F(1, 1)-felbontható, ha ,Egymástól függetlenül bizonyította , illetve következik -ből, 11-es girthparaméterre vonatkozó eredményeit továbbfejlesztve, majd 10-es girthre és 9-es girthre.. vagy ha minden köre vagy háromszög, vagy legalább 8 élből áll, melyek nem tartoznak háromszöghöz., még ha nem is állítja explicit módon. (1, 5)-felbontható, ha nem rendelkezik 4 hosszúságú körrel., továbbfejlesztve , majd eredményeit. Minden külsíkgráf F(2, 0)-felbontható és (1, 3)-felbontható.Explicit hivatkozás nélkül bizonyították.
Fordítás
Jegyzetek
Hivatkozások kronologikus sorrendben
Kategória:Gráfinvariánsok Kategória:Gráfelméleti objektumok