Ugrás a tartalomhoz

(a, b)-felbontás

Ellenőrzött
A Wikipédiából, a szabad enciklopédiából

A matematika, azon belül a gráfelmélet területén egy irányítatlan gráf (ab)-felbontása vagy (ab)-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(ab)-felbontásról beszélünk.

Egy a arboricitású gráf (a, 0)-felbontható. Minden (a0)-felbontásra, illetve (a1)-felbontásra igaz, hogy egyben F(a0)-felbontás, illetve F(a1)-felbontás.

Gráfosztályok

[szerkesztés]
  • Minden síkbarajzolható gráf F(2, 4)-felbontható.[1]
  • Minden síkbarajzolható gráf, melynek girthparamétere legalább :
    • F(2, 0)-felbontható, ha .[2]
    • (1, 4)-felbontható, ha .[3]
    • F(1, 2)-felbontható, ha .[4]
    • F(1, 1)-felbontható, ha ,[5] vagy ha minden köre vagy háromszög, vagy legalább 8 élből áll, melyek nem tartoznak háromszöghöz.[6]
    • (1, 5)-felbontható, ha nem rendelkezik 4 hosszúságú körrel.[7]
  • Minden külsíkgráf F(2, 0)-felbontható[2] és (1, 3)-felbontható.[8]

Fordítás

[szerkesztés]
  • Ez a szócikk részben vagy egészben az (a, b)-decomposition című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek

[szerkesztés]
  1. (Gonçalves 2009), megsejtője (Balogh et al. 2005). (Nash-Williams 1964) eredményeit (Balogh et al. 2005) fejlesztette tovább.
  2. a b (Nash-Williams 1964)-ből következik.
  3. (He et al. 2002)
  4. (Montassier et al. 2012)-ből következik, (He et al. 2002), majd (Kleitman 2008) eredményeit továbbfejlesztve.
  5. Egymástól függetlenül bizonyította (Wang & Zhang 2011), illetve következik (Montassier et al. 2012)-ből, (He et al. 2002) 11-es girthparaméterre vonatkozó eredményeit továbbfejlesztve, majd (Bassa et al. 2010) 10-es girthre és (Borodin et al. 2008a) 9-es girthre..
  6. (Borodin et al. 2009b), még ha nem is állítja explicit módon.
  7. (Borodin et al. 2009a), továbbfejlesztve (He et al. 2002), majd (Borodin et al. 2008b) eredményeit.
  8. Explicit hivatkozás nélkül (Guan & Zhu 1999) bizonyították.

Hivatkozások kronologikus sorrendben

[szerkesztés]