(a, b)-felbontás

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[szerkesztés]

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

↑ (Gonçalves 2009), megsejtője (Balogh et al. 2005). (Nash-Williams 1964) eredményeit (Balogh et al. 2005) fejlesztette tovább.
↑ ^a ^b (Nash-Williams 1964)-ből következik.
↑ (He et al. 2002)
↑ (Montassier et al. 2012)-ből következik, (He et al. 2002), majd (Kleitman 2008) eredményeit továbbfejlesztve.
↑ 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..
↑ (Borodin et al. 2009b), még ha nem is állítja explicit módon.
↑ (Borodin et al. 2009a), továbbfejlesztve (He et al. 2002), majd (Borodin et al. 2008b) eredményeit.
↑ Explicit hivatkozás nélkül (Guan & Zhu 1999) bizonyították.

Hivatkozások kronologikus sorrendben[szerkesztés]

Nash-Williams, Crispin St. John Alvah (1964). „Decomposition of finite graphs into forests”. Journal of the London Mathematical Society 39 (1), 12. o. DOI:10.1112/jlms/s1-39.1.12.
Guan, D. J. (1999. április 17.). „Game chromatic number of outerplanar graphs”. Journal of Graph Theory 30 (1), 67–70. o. DOI:<67::aid-jgt7>3.0.co;2-m 10.1002/(sici)1097-0118(199901)30:1<67::aid-jgt7>3.0.co;2-m.
He, Wenjie (2002. április 17.). „Edge-partitions of planar graphs and their game coloring numbers”. Journal of Graph Theory 41, 307–311. o. DOI:10.1002/jgt.10069.
Balogh, József (2005. április 17.). „Covering planar graphs with forests”. Journal of Combinatorial Theory, Series B 94 (1), 147–158. o. DOI:10.1016/j.ejc.2007.06.020.
Borodin, Oleg V. (2008. április 17.). „Decomposing a planar graph with girth 9 into a forest and a matching”. European Journal of Combinatorics 29 (5), 1235–1241. o. DOI:10.1016/j.ejc.2007.06.020.
Borodin, Oleg V. (2008. április 17.). „M-Degrees of Quadrangle-Free Planar Graphs”. Journal of Graph Theory 60 (1), 80–85. o. DOI:10.1002/jgt.20346.
Kleitman, Daniel J. (2008. április 17.). „Partitioning the Edges of a Girth 6 Planar Graph into those of a Forest and those of a Set of Disjoint Paths and Cycles”. Manuscript.
Gonçalves, Daniel (2009. április 17.). „Covering planar graphs with forests, one having bounded maximum degree”. Journal of Combinatorial Theory, Series B 99 (2), 314–322. o. DOI:10.1016/j.jctb.2008.07.004.
Borodin, Oleg V. (2009. április 17.). „Decompositions of Quadrangle-Free Planar Graphs”. Discussiones Mathematicae Graph Theory 29, 87–99. o. DOI:10.7151/dmgt.1434.
Borodin, Oleg V. (2009. április 17.). „Planar graphs decomposable into a forest and a matching”. Discrete Mathematics 309 (1), 277–279. o. DOI:10.1016/j.disc.2007.12.104.
Bassa, A. (2010. április 17.). „Partitioning a Planar Graph of Girth 10 into a Forest and a Matching”. European Journal of Combinatorics 124 (3), 213–228. o. DOI:10.1111/j.1467-9590.2009.00468.x.
Wang, Yingqian (2011. április 17.). „Decomposing a planar graph with girth at least 8 into a forest and a matching”. Discrete Mathematics 311 (10-11), 844–849. o. DOI:10.1016/j.disc.2011.01.019.
Montassier, Mickaël (2012. április 17.). „Decomposing a graph into forests”. Journal of Combinatorial Theory, Series B 102 (1), 38–52. o. DOI:10.1016/j.jctb.2011.04.001.

[1] (Gonçalves 2009), megsejtője (Balogh et al. 2005). (Nash-Williams 1964) eredményeit (Balogh et al. 2005) fejlesztette tovább.

[NW-2] (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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]