( a , b )分解

グラフ理論において、無向グラフの( a , b )-分解とは、その辺を a + 1 個の集合に分割し、それぞれの集合が森を誘導するものの、次数が最大bのグラフを誘導するものは 1 つだけであるような分割のことである。このグラフも森である場合、これをF( a , b )-分解と呼ぶ。

樹形度aのグラフは ( a , 0) 分解可能である。すべての ( a , 0 ) 分解または ( a , 1 ) 分解は、それぞれ F( a , 0 ) 分解または F( a , 1 ) 分解である。

グラフクラス

すべての平面グラフはF(2, 4)分解可能である。^{[ 1 ]}
すべての平面グラフ $G$ $G$ 少なくとも周囲径 $g$ $g$ は
- F(2, 0)分解可能 $g\geq 4$ [ ²^]
- （1、4 ）分解可能 $g\geq 5$ [ ³^]
- F(1, 2)分解可能 $g\geq 6$ [ ⁴^]
- F(1, 1)分解可能 $g\geq 8$ [ ⁵^]または、すべてのサイクル^が $G$ 三角形であるか、少なくとも 8 つの辺を持つ三角形に属さないサイクルである。^{[ 6 ]}
- （1, 5）分解可能 $G$ 4サイクルはありません。^{[ 7 ]}
すべての外平面グラフはF(2, 0)分解可能^{[ 2 ]}であり、(1, 3)分解可能である^{[ 8 ] 。}

注記

↑ Gonçalves (2009)は Balogh et al. (2005)によって推測された。Nash -Williams (1964)とBalogh et al. (2005)によって結果が改善された。
1 2ナッシュ＝ウィリアムズ（1964）によって示唆されている。
↑ He et al. (2002)
↑ Montassier et al. (2012)によって示唆され、 He et al. (2002)によって結果が改善され、その後Kleitman (2008)によって改善されました。
↑ Wang & Zhang (2011)によって独立して証明され、 Montassier et al. (2012)によって示唆され、 He et al. (2002)による 11 周径に関する結果を改善し、 Bassa et al. (2010)による 10 周径に関する結果、 Borodin et al. (2008a)による 9 周径に関する結果を改善した。
↑ Borodin et al. (2009b)は明示的に述べられていなくても、
↑ Borodin et al. (2009a)は He et al. (2002)の結果を改善し、その後Borodin et al. (2008b) が研究を行った。
↑ Guan & Zhu (1999)によって明示的な参照なしに証明された。

参考文献（時系列順）

Nash-Williams, Crispin St. John Alvah (1964). 「有限グラフの森への分解」. Journal of the London Mathematical Society . 39 (1): 12. doi : 10.1112/jlms/s1-39.1.12 . MR 0161333 .
Guan, DJ; Zhu, Xuding (1999). "外平面グラフのゲーム彩色数". Journal of Graph Theory . 30 (1): 67–70 . doi : 10.1002/(sici)1097-0118(199901)30:1 < 67::aid-jgt7 > 3.0.co ; 2-m .
He, Wenjie; Hou, Xiaoling; Lih, Ko-Wei; Shao, Jiating; Wang, Weifan; Zhu, Xuding (2002). "平面グラフのエッジ分割とそのゲーム彩色数" . Journal of Graph Theory . 41 (4): 307–311 . doi : 10.1002/jgt.10069 . S2CID 20929383 .
バログ、ヨーゼフ。コチョル、マーティン。アンドラーシュ州プルハール;ユウ・シンシン（2005）。「平面グラフをフォレストで覆う」。組み合わせ理論ジャーナル、シリーズ B。94 (1): 147–158。土井: 10.1016/j.ejc.2007.06.020。
Borodin, Oleg V.; Kostochka, Alexandr V.; Sheikh, Naeem N.; Yu, Gexin (2008). "周長9の平面グラフを森とマッチングに分解する" . European Journal of Combinatorics . 29 (5): 1235–1241 . doi : 10.1016/j.ejc.2007.06.020 .
ボロディン、オレグ V.コストチカ、アレクサンドル 5 世。シェイク、ナイーム N.ユウ、ゲシン（2008）。「四角形のない平面グラフのM次数」 (PDF)。グラフ理論ジャーナル。60 (1): 80 ～ 85。CiteSeerX 10.1.1.224.8397。土井：10.1002/jgt.20346。S2CID 7486622。
Kleitman, Daniel J. (2008). 「周長6の平面グラフのエッジをフォレストのエッジと互いに素なパスとサイクルの集合のエッジに分割する」。原稿。
Gonçalves, Daniel (2009). 「最大次数が制限された森林で平面グラフを覆う」 . Journal of Combinatorial Theory, Series B. 99 ( 2): 314–322 . doi : 10.1016/j.jctb.2008.07.004 .
ボロディン、オレグ V.イワノバ、アンナ O.コストチカ、アレクサンドル 5 世。シェイク、ナイーム N. (2009)。「四角形のない平面グラフの分解」(PDF)。数学グラフ理論に関するディスカッション。29 : 87–99。CiteSeerX 10.1.1.224.8787 。土井: 10.7151/dmgt.1434。
ボロディン、オレグ V.イワノバ、アンナ O.コストチカ、アレクサンドル 5 世。シェイク、ナイーム N. (2009)。「フォレストとマッチングに分解可能な平面グラフ」。離散数学。309 (1): 277–279。土井: 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, P.-O.; Pylyavskyy, P.; Rademacher, L.; Riehl, A.; Rios, M.; Samuel, J.; Tenner, BE ; Vijayasarathy, A.; Zhao, L. (2010). "Partitioning a Planar Graph of Girth 10 into a Forest and a Matching". European Journal of Combinatorics . 124 (3): 213– 228. doi : 10.1111/j.1467-9590.2009.00468.x . S2CID 120663098 .
Wang, Yingqian; Zhang, Qijun (2011). "周長が少なくとも 8 の平面グラフを森とマッチングに分解する" . Discrete Mathematics . 311 ( 10–11 ): 844–849 . doi : 10.1016/j.disc.2011.01.019 .
モンタシエ、ミカエル。オッソナ・デ・メンデス、パトリス;アンドレ、ラスパウド。朱、徐鼎 (2012)。「グラフをフォレストに分解する」。組み合わせ理論ジャーナル、シリーズ B。102 (1): 38–52。土井: 10.1016/j.jctb.2011.04.001。

[1] Gonçalves (2009)は Balogh et al. (2005)によって推測された。Nash -Williams (1964)とBalogh et al. (2005)によって結果が改善された。

[NW-2] 1 2ナッシュ＝ウィリアムズ（1964）によって示唆されている。

[3] He et al. (2002)

[4] Montassier et al. (2012)によって示唆され、 He et al. (2002)によって結果が改善され、その後Kleitman (2008)によって改善されました。

[5] Wang & Zhang (2011)によって独立して証明され、 Montassier et al. (2012)によって示唆され、 He et al. (2002)による 11 周径に関する結果を改善し、 Bassa et al. (2010)による 10 周径に関する結果、 Borodin et al. (2008a)による 9 周径に関する結果を改善した。

[6] Borodin et al. (2009b)は明示的に述べられていなくても、

[7] Borodin et al. (2009a)は He et al. (2002)の結果を改善し、その後Borodin et al. (2008b) が研究を行った。

[8] Guan & Zhu (1999)によって明示的な参照なしに証明された。

[ 1 ]

2

3

4

5

[ 6 ]

[ 7 ]

[ 8 ] 。