(a, b)-felbontás

Innen: testwiki
Ugrás a navigációhoz Ugrás a kereséshez

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ó.[1]
  • Minden G síkbarajzolható gráf, melynek girthparamétere legalább g:
    • F(2, 0)-felbontható, ha g≥4.[2]
    • (1, 4)-felbontható, ha g≥5.[3]
    • F(1, 2)-felbontható, ha g≥6.[4]
    • F(1, 1)-felbontható, ha g≥8,[5] vagy ha G 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 G 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

Jegyzetek

Sablon:Reflist

Hivatkozások kronologikus sorrendben

Sablon:Refbegin

Sablon:Refend

  1. ↑ Sablon:Harvtxt, megsejtője Sablon:Harvtxt. Sablon:Harvtxt eredményeit Sablon:Harvtxt fejlesztette tovább.
  2. ↑ 2,0 2,1 Sablon:Harvtxt-ből következik.
  3. ↑ Sablon:Harvtxt
  4. ↑ Sablon:Harvtxt-ből következik, Sablon:Harvtxt, majd Sablon:Harvtxt eredményeit továbbfejlesztve.
  5. ↑ Egymástól függetlenül bizonyította Sablon:Harvtxt, illetve következik Sablon:Harvtxt-ből, Sablon:Harvtxt 11-es girthparaméterre vonatkozó eredményeit továbbfejlesztve, majd Sablon:Harvtxt 10-es girthre és Sablon:Harvtxt 9-es girthre..
  6. ↑ Sablon:Harvtxt, még ha nem is állítja explicit módon.
  7. ↑ Sablon:Harvtxt, továbbfejlesztve Sablon:Harvtxt, majd Sablon:Harvtxt eredményeit.
  8. ↑ Explicit hivatkozás nélkül Sablon:Harvtxt bizonyították.
A lap eredeti címe: „https://hu.wiki.beta.math.wmflabs.org/w/index.php?title=(a,_b)-felbontás&oldid=3738”