グラフの禁止構造条件について 古谷倫貴 ( 北里大学一般教育部 )
話の流れ 1. 禁止部分グラフ a. 問題設定 b. ハミルトン閉路のための禁止部分グラフ c. 完全マッチングのための禁止部分グラフ d. 禁止部分グラフ条件の完全決定の難易 2. 自明な禁止部分グラフ条件 3. 禁止部分グラフ条件の比較
問題設定 グラフのある性質 P について,P のための ( 十分 ) 条件として良いものを考えたい. 例えば 完全マッチングを持つ という性質に着目してみる. 完全マッチング : グラフの全頂点を用いる独立辺の集合 グラフに完全マッチングが存在するための有名な必要十分があるが, それについてはとりあえず無視する.
問題設定完全マッチングを持たないグラフとは? 奇位数グラフは完全マッチングを持たない 下は完全マッチングを持たない偶位数グラフの無限列 奇数 2k + 1 奇数 K 2m 1 K 2m 1 K 2m 1 K 2k 1 このグラフたちには共通しての形が現れている! ( このグラフを claw という ) 偶位数グラフに claw の構造を 禁止 すれば, 完全マッチングの存在が言える?
問題設定 G をグラフとする. S V G について, uv E G u, v S を辺集合とする S 上のグラフ G S を,S で誘導される G の誘導部分グラフという. G がグラフ H と同型な誘導部分グラフを含むとき,H G と書く. H G となるとき,G は H-free であるという. 注意 2 つのグラフ H 1, H 2 に対して,H 1 H 2 が成り立つとき, 任意の H 1 -free グラフは H 2 -free である. 特に,H 1 -free グラフのクラスより,H 2 -free グラフのクラスの方が大きい.
問題設定 定理 (Sumner, 1974) 偶位数連結 claw-free グラフは完全マッチングを持つ. ( 証明 ) ある偶位数連結 claw-free グラフ G が完全マッチングを持たないと仮定する. すると 1- 因子定理 (Tutte, 1947) より, ある X V G に対して, が成り立つ. G X の奇位数成分の個数 X + 2 このような X を最小にとると,X の頂点は G X の奇位数連結成分のうち, 少なくとも 3 個と隣接する. claw が誘導部分グラフとして見つかり, 矛盾する.
ハミルトン閉路のための禁止部分グラフ グラフが ハミルトン閉路を持つ という性質について, グラフの禁止条件は? ハミルトン閉路 : グラフのすべての頂点を通る閉路 ハミルトン閉路を持つグラフは 2- 連結であるから, 対象のグラフは 2- 連結グラフに限る. 下はハミルトン閉路を持たない 2- 連結グラフの無限列 これらの共通の誘導部分グラフは? (P 3 ) が最大の共通の連結誘導部分グラフ.
ハミルトン閉路のための禁止部分グラフ 命題連結 P 3 -free グラフ G は完全グラフである. ( 証明 ) G が完全グラフでないと仮定すると, ある非隣接な 2 頂点が存在する. G は連結であるから, 距離が 2 となる 2 頂点 u, v が存在する. このとき,w N G u N G v について,uwv が誘導 P 3 となる. 命題 2- 連結 P 3 -free グラフはハミルトン閉路を持つ.
ハミルトン閉路のための禁止部分グラフ H をいくつかの連結グラフからなる集合とする. グラフ G が, H H, H G を満たすとき,G は H-free であるという. いくつかの連結グラフからなる集合 H 1, H 2 に対して, H 2 H 2, H 1 H 1 s. t. H 1 H 2 が成り立つとき,H 1 H 2 と書く. 注意 H 1 H 2 ならば任意の H 1 -free グラフは H 2 -free である.
ハミルトン閉路のための禁止部分グラフ 定理 (Duffus et al., 1981) 2- 連結 claw, N -free グラフはハミルトン閉路を持つ. 定理 (Broesma and Veldman, 1990) 2- 連結 claw, P 6 -free グラフはハミルトン閉路を持つ. 定理 (Bedrossian, 1991) 2- 連結 claw, B 1,2 -free グラフはハミルトン閉路を持つ.
ハミルトン閉路のための禁止部分グラフ 定理 (Bedrossian, 1991) 2 つの連結グラフ H 1, H 2 が命題 2- 連結 H 1, H 2 -free グラフはハミルトン閉路を持つ を満たすための必要十分条件は, (1) H 1, H 2 claw, N (2) H 1, H 2 claw, P 6 (3) H 1, H 2 claw, B 1,2 のいずれかとなることである.
ハミルトン閉路のための禁止部分グラフ 定理 (Faudree et al., 1995) 2- 連結 claw, Z 3 -free グラフは, 以下の 2 つを除きハミルトン閉路を持つ. 2- 連結 claw, Z 3 -free グラフはハミルトン閉路を持つ という命題は, 反例があるため成り立たない. ( よって Bedrossian の特徴付けに claw, Z 3 は現れない ) しかし, 反例が2 個しか存在しないことが分かっているため, claw, Z 3 はハミルトン閉路のための禁止条件と見なして良さそう.
ハミルトン閉路のための禁止部分グラフ 定理 (Faudree and Gould, 1997) 2 つの連結グラフ H 1, H 2 が命題 位数が十分大きい 2- 連結 H 1, H 2 -free グラフはハミルトン閉路を持つ を満たすための必要十分条件は, (1) H 1, H 2 claw, N (2) H 1, H 2 claw, P 6 (3) H 1, H 2 claw, B 1,2 (4) H 1, H 2 claw, Z 3 のいずれかとなることである. 小さい例外グラフを認めて, 今後は 位数が十分大きい という仮定の下で問題を考える.
ハミルトン閉路のための禁止部分グラフ 位数が十分大きい 2- 連結 H 1, H 2, H 3 -free グラフはハミルトン閉路を持つ を満たす 3 つの連結グラフ H 1, H 2, H 3 の特徴付けも知られており, 本質的に 12 種類に分類される. (Brousek, 2002; Faudree et al. 2004)
ハミルトン閉路のための禁止部分グラフ 禁止するグラフの個数を増やすと, 命題は ( ある意味で ) 強くなる. 定理 (Brousek, 2002) 位数が十分大きい 2- 連結 claw, B 1,3, R -free グラフはハミルトン閉路を持つ. claw, Z 3 claw, B 1,3, R なので, 位数が十分大きい 2- 連結 claw, Z 3 -free グラフはハミルトン閉路を持つ (Faudree et al., 1995) が導かれる.
ハミルトン閉路のための禁止部分グラフ 定理 (Fujisawa, 2012) 2 つの連結グラフ H 1, H 2 が命題 位数が十分大きい 3- 連結 H 1, H 2 -free グラフはハミルトン閉路を持つ を満たすならば, ある i 1,2 に対して H i K 1,3 かつ (1)H 3 i P 10 (2)H 3 i は K 3 から 3 本の点素な道を出した位数 12 以下のグラフ (3)2 つの K 3 を長さ 1,3,5,7 いずれかの道で結んだグラフ のいずれかとなる.
ハミルトン閉路のための禁止部分グラフ 予想 (Matthews and Sumner, 1984) 4- 連結 claw-free グラフは, ハミルトン閉路を持つ. 定理 (Kaiser and Vrana, 2012) 最小次数 6 以上の 5- 連結 claw-free グラフは, ハミルトン閉路を持つ.
ハミルトン閉路のための禁止部分グラフ ( この講演での ) グラフの禁止条件 性質 P に対して, それを見つけるためのグラフの禁止条件を見つけたい. 性質 P の自明な十分条件 ( 完全マッチング : 偶位数, ハミルトン閉路 :2- 連結性 ) は仮定しておく. ただし, より強い仮定 ( ハミルトン閉路について k- 連結 ) を仮定することもある. 対象のグラフは, 位数が十分大きいもののみを考える. 一般に, 禁止するグラフの個数を増やすと考えるべき状況も増えて, 強い命題が得られる.
完全マッチングのための禁止部分グラフ 定理 (Sumner, 1974) 偶位数連結 claw-free グラフは完全マッチングを持つ. 定理 (Plummer and Saito, 2005) 連結グラフ H が命題 位数が十分大きい偶位数連結 H-free グラフは完全マッチングを持つ を満たすための必要十分条件は,H claw となることである.
完全マッチングのための禁止部分グラフ 定理 (Fujita et al., 2006) 2 つの連結グラフ H 1, H 2 が命題 位数が十分大きい偶位数連結 H 1, H 2 -free グラフは完全マッチングを持つ を満たすための必要十分条件は, H 1, H 2 なることである. claw と
完全マッチングのための禁止部分グラフ 定理 (Ota et al., 2010) 3 つの連結グラフ H 1, H 2, H 3 が命題 位数が十分大きい偶位数連結 H 1, H 2, H 3 -free グラフは完全マッチングを持つ を満たすための必要十分条件は, (1) H 1, H 2, H 3 K 1,3 p 4, q 2 (2) H 1, H 2, H 3 K 1,p, Y q, Q 1,r p 4, q 4, r 3 (3) H 1, H 2, H 3 K 1,p, P 4, Q 2,r p 4, r 3 のいずれかとなることである. n 頂点 k 頂点 K n Y n Q k,n
完全マッチングのための禁止部分グラフ 定理 (Ota and Sueiro, 2013) 連結グラフの集合 H が命題 位数が十分大きい偶位数連結 H-free グラフは完全マッチングを持つ 禁止条件のを満たすための必要十分条件は, 完全決定 H K 1,p, Y q, W r, Z + i,s 0 i q 2 p 4, q 2, r 2, s 3 となることである. n 頂点 Y n K n m 頂点 K n + W n Z n,m
完全マッチングのための禁止部分グラフ 連結度を上げると? 定理 (Sumner, 1975; Plummer and Saito, 2005) k 2 を整数とする. 連結グラフ H が命題 位数が十分大きい偶位数 k- 連結 H-free グラフは完全マッチングを持つ を満たすための必要十分条件は,H K 1,k+1 となることである.
完全マッチングのための禁止部分グラフ 定理 (Fujisawa et al., 2011) k 2 を整数とする. 2 つの連結グラフ H 1, H 2 が命題 位数が十分大きい偶位数 k- 連結 H 1, H 2 -free グラフは完全マッチングを持つ を満たすための必要十分条件は, (1) H 1, H 2 K 1,k+1 (2) H 1, H 2 K 1,k+2, F p 1 p k 2 + 1 n 頂点 のいずれかとなることである. F n
完全マッチングのための禁止部分グラフ 連結度の高いグラフにおいては,star を禁止すれば完全マッチングが存在する. 禁止する star に対して, 連結度を もっと 大きくすると, マッチングに関してより強い性質が得られるのでは? 整数 m 0, n 0 に対し, グラフ G が E m, n を満たすとは, 辺素な任意の 2 つのマッチング M, N E G M = m, N = n について,G が M F かつ F N = なる完全マッチング F = F M,N を持つことである.
完全マッチングのための禁止部分グラフ 定理 (Aldred and Plummer, 1999) k 1, m 0, n 0 を,m + n 1 かつ n k 2m+1 満たす整数とするとき, 位数が十分大きい偶位数 k- 連結 K k 2m n+2 -free グラフは E m, n を満たす. 定理 (Egawa and F., 2016) k 4, m 0, n 3 を, k 2m+2 2 n k 2m 1 を 満たす整数とするとき, 位数が十分大きい偶位数 k- 連結 -free グラフは E m, n を満たす. K k m+2 2 n に依存しない禁止条件 2 を
禁止部分グラフ条件の完全決定の難易 グラフの禁止条件が,( 自明な必要条件下で ) 完全決定している問題 HIST (F. and Tsuchiya, 2013) HIST: 葉以外の頂点の次数が 3 以上の全域木 0 < t < 1 に対する t-タフ (Ota and Sueiro, 2013) S G が t-タフ S cutset of G, t # of compo. of G S 全域 2- 歩道 (F., 2014) k- 歩道 : 各頂点を高々 k 回通るような歩道
禁止部分グラフ条件の完全決定の難易 命題 (Jackson and Wormald, 1990) k 2 を整数とする. グラフ G が全域 k- 歩道を持つならば,G は 1/k - タフである. また, 1/k - タフであるが全域 k- 歩道を持たないグラフの無限列が存在する. 一方で, 1/2 - タフのための禁止条件 と 全域 2- 歩道のための禁止条件 は一致する! 問題グラフの 2 つの ( 強弱のある ) 性質について, それらのための禁止条件が等しいものは他にあるか?
禁止部分グラフ条件の完全決定の難易 グラフの禁止条件として, H 1, H 2 -free の形でも未決定の問題 k 3 に対する全域 k- 木 (cf. Ota and Sugiyama, 2010) k- 木 : すべての頂点の次数が k 以下の木 全域部分 Halin グラフ (cf. Chen et al., 2017+) Halin グラフ :HIT の葉を閉路で繋いだ平面グラフ 辺支配閉路 (cf. Chiba, F. and Tsuchiya, 2015, 2016) 辺支配閉路 : 取り除くと孤立点のみが残る閉路 問題グラフの禁止条件を考えるに当たって, 簡単 難しいの違いは何か?
自明な禁止部分グラフ条件 禁止部分グラフを考えるとき, 位数が十分大きいことを仮定するのが通常であった. そこに弊害も 定理 (Fujisawa et al., 2013) 5- 連結 claw, K 4 -free グラフは, 正二十面体グラフに限る. 特に 位数 13 以上の 5- 連結 claw, K 4 -free グラフのクラス は ( 空なので ) どのような性質でも満たす. このようなグラフのクラスを考えることは無駄であるが, 禁止条件を考える上では避けられないので, 予め特定しておきたい.
自明な禁止部分グラフ条件 k 1 を整数とする. G k を k- 連結グラフ全体からなる集合とする. 連結グラフの集合 H に対して, G k H = G G k G は H-free と定める. 問題 G k H < を満たすような H を決定せよ.
自明な禁止部分グラフ条件 定理 (Diestel) 連結グラフの集合 H が G 1 H 必要十分条件は, H K p, P q, K 1,r p 1, q 1, r 1 となることである. < を満たすための ( 必要性の証明 ) K 1,n n 1 は無限集合であるから, ある r 1 に対して K 1,r は H-free でない. よって, H H s. t. H K 1,r となる. したがって,H K 1,r となる. 同様に, K n n 1 と P n n 1 を考えれば, ある p 1, q 1 について H K p と H P q となる.
自明な禁止部分グラフ条件 ( 十分性の証明 ) G を連結 K p, P q, K 1,r -free グラフとする. p 2 または q 2 または r = 1 だと,G K 1 となるので, p 3, q 3, r 2 として良い. G は P q -free なので,diam G q 2. x V G を d G x = Δ G を満たす頂点とする. G は K p, K 1,r -free なので,N G x はサイズ p 1 のクリークも, サイズ r の独立集合も含まない. よって Δ G = d G x R p 1, r (R, : ラムゼー数 ). 以上より V G Δ G diam G R p 1, r 1 q 2.
自明な禁止部分グラフ条件連結度を上げると? 命題 (Fujisawa et al., 2013) k 1 を整数とする. 連結グラフ H が G k H < を満たすための必要十分条件は,H K 2 となることである.
自明な禁止部分グラフ条件 命題 (Fujisawa et al., 2013) k 1 を整数とする. 連結グラフ H 1, H 2 が G k H 1, H 2 < を満たすならば, p 3, 2 r k s. t. H 1, H 2 K p, K 1,r となる. 定理 (Fujisawa et al., 2013) 1 k 6 を整数とする. 連結グラフ H 1, H 2 が G k H 1, H 2 必要十分条件は, < を満たすための (1) H 1, H 2 K p, K 1,2 p 3 (2) H 1, H 2 K 3, K 1,r 3 r k if 3 k 6 (3) H 1, H 2 K 4, K 1,3 if 5 k 6 のいずれかとなることである.
自明な禁止部分グラフ条件 定理 (F. and Okubo, 2015) 連結グラフ H 1,, H 4 が G 2 H 1,, H 4 < を満たすための必要十分条件は以下のいずれかとなることである. (1) H 1,, H 4 K 3, P 5, K 2,r r 2 (2) H 1,, H 4 K 3, P 6, K 2,2 (3) H 1,, H 4 1 K 3, P 6, K 2,r, H s r 3, s 2 (4) H 1,, H 4 2 K 3, P 7, K 2,2, H s s 2 (5) H 1,, H 4 K 3, P q, K 2,2, H3 s q 8, s 3 (6) H 1,, H 4 K 3, P q, K 2,r, H4 s q 7, r 2, s 3, q, r 7,2 (7) H 1,, H 4 K p, P 5, K 2,r, H5 s p 4, r 2, s 2 (8) H 1,, H 4 K p, P 6, K 2,2, H5 s p 4, s 2
自明な禁止部分グラフ条件 H n 1 H n 2 H n 3 H n 4 H n 5 大抵の場合は禁止するグラフを制限するので, 当初の目的のためにはこの位調べておけば十分.
自明な禁止部分グラフ条件 G 3 H 1, H 2, H 3 < について (Egawa and F., 2014; Egawa et al., 2015) H 1, H 2, H 3 の完全な特徴付けには程遠い
禁止部分グラフ条件の比較 連結グラフの 2 つの集合 H 1, H 2 について, ほとんど G k H 1 G k H 2 ほとんど G k H 1 = G k H 2 などが分かれば, 禁止条件の問題について, 一方の情報が他方に知見を与える. H 1 H 2 であれば,G k H 1 G k H 2 であったが, それ 以外の状況でも ( ほとんど ) G k H 1 G k H 2 が成り立つ ことはあるか? 問題 G k H 1 G k H 2 < や G k H 1 G k H 2 < を 満たすような H 1, H 2 を決定せよ.
禁止部分グラフ条件の比較 G 1 H 1 G 1 H 2 < かつ H 1 H 2 を満たす H 1, H 2 は存在するか? 命題 下のグラフ H 1, H 2 について, G 1 H 1 G 1 H 2 < かつ H 1 H 2 を満たす. H 1 H 2 rep. 十分大のトーラス上 6 正則三角形分割 ( 証明 ) H 1 H 2 は自明. G 1 H 1 G 1 H 2 = H 2, すなわち H 2 を誘導部分グラフに持つ連結 H 1 -free グラフは H 2 のみを示せば良い.
禁止部分グラフ条件の比較 G 1 H 1 G 1 H 2 < かつ H 1 H 2 を満たす H 1, H 2 の特徴付けは難しそう 定理 (Fujita et al., 2013) 連結グラフ H 1, H 2 が G 1 H 1 G 1 H 2 < かつH 1 H 2 を満たすならば, 以下が成り立つ. (1)δ H 1 = 1, Δ H 1 = V H 1 1 (2) a 1, a 2 V H 1 s. t. N G a 1 = N G a 2 (3) b 1, b 2 V H 1 s. t. N G b 1 = N G b 2 (4) V H 2 2 V H 1 3 (5)δ H 2 V H 1 2
禁止部分グラフ条件の比較 G 1 H 1 G 1 H 2 < を満たす H 1, H 2 は? を満たすための必要十分条件は H 1 = H 2 となることである. 定理 (Fujita et al., 2013) 位数 3 以上の連結グラフ H 1, H 2 が G 1 H 1 G 1 H 2 < ( 必要性の証明 ) 背理法と対称性より H 1 H 2 と仮定する. H 1 = P 3 と仮定すると,G 1 H 1 = K n n 1 となる. H 1 H 2, すなわち H 2 は H 1 -free であるから,H 2 は完全グラフである. このとき, K n n V H 2 G 1 H 1 G 1 H 2 となり, G 1 H 1 G 1 H 2 < に反する. よって H 1 P 3 である.
禁止部分グラフ条件の比較 A 1 = H 2 K n n 1 は H 2 -free でない連結グラフの 無限集合であるから,A 1 G 1 G 1 H 2 を満たす. G 1 H 1 G 1 H 2 < であるから, n 1 1, H 2 H 2 s. t. H 1 = H 2 K n1 となる. A 2 = n 1 について同様に考えると, H 2 P n n 2 1, H 2 H 2 s. t. H 1 = H 2 P n2 となる. 特に Δ H 1 = V H 1 1, δ H 1 = 1 となる. また,A 2 の P n の根本の選び方より,δ H 2 V H 1 2.
禁止部分グラフ条件の比較 以上より, 以下のようになる. H 1 = x H 2 d H1 x = 1 よって, V H 2 N H2 x V H 1 2 となる. したがって, V H 2 = δ H 2 + 1 + V H 2 N H2 x 2 V H 1 3. V H 2 > V H 1 であれば H 2 H 1 なので, 同じ議論により V H 1 2 V H 2 3 が得られて矛盾. V H 2 V H 1 であれば V H 1 = V H 2 = 3 と なり,H 1 H 2 より H 1, H 2 = P 3, K 3 となって, 最初 の議論で矛盾.
禁止部分グラフ条件の比較 を満たすための必要十分条件は H 1 = H 2 となることである. 定理 (Fujita et al., 2013) k 1 を整数とする. 位数 3 以上の連結グラフ H 1, H 2 が G k H 1 G k H 2 < 定理 (Fujita et al., 2013) 連結グラフ H と H 3 なる連結グラフの集合 H が G 1 H G 1 H < を満たすならば, (1)H H (2)H = K 3 かつ H = 3 のいずれかとなる. G 1 K 3 G 1 K 4,, < G 1 K 3 G 1 K 5,, <
禁止部分グラフ条件の比較 ここで, G 1 K 3 G 1 K 4,, < という事実に着目 する. この右側は,K 3 に1 頂点を加えて適当な辺を加えた集合で ある. 一般に, 連結グラフ H に対して,H に 1 頂点 x を加え, x と H を 1 本以上の辺で結んで得られるグラフの集合を H H + と表す. 注意連結グラフ H に対して,G 1 H G 1 H H + = H となる.
禁止部分グラフ条件の比較 グラフの禁止条件で重要な,claw に注目する. 注意 + H claw = H 1 H 2 H 3 H 4 H 5 H 6 H 7.
禁止部分グラフ条件の比較 定理 (F. and Yokota, 2017+) + 整数 k 1 と H H claw が G k claw G k H < を満たすための必要十分条件は以下のいずれかとなることである. (1)k = 1 かつ, H 1,, H 6 H (2)k = 2 かつ, H 1,, H 6 H または H 1,, H 4, H 7 H (3)k = 3 かつ, H 1,, H 5 H または H 1,, H 4, H 7 H (4)k 4 かつ, H 1, H 2, H 5, H 6 H または H 1, H 2, H 3, H 6, H 7 H または H 1,, H 5 H または H 1,, H 4, H 7 H
禁止部分グラフ条件の比較 予想 (Matthews and Sumner, 1984) 4- 連結 claw-free グラフは, ハミルトン閉路を持つ. 定理 (F. and Yokota, 2017+) Matthews-Sumner 予想は, 以下と同値である. (1)4- 連結 H 1, H 2, H 5, H 6 -free グラフはハミルトン閉路を持つ. (2)4- 連結 H 1, H 2, H 3, H 6, H 7 -free グラフはハミルトン閉路を持つ. (3)4- 連結 H 1,, H 5 -free グラフはハミルトン閉路を持つ. (4)4- 連結 H 1,, H 4, H 7 -free グラフはハミルトン閉路を持つ.
禁止部分グラフ条件の比較 定理 (Chiba, Fujisawa, F. and Ikarashi, 2017) H 1, H 2, H 3 を位数 3 以上の連結グラフとする. δ H 1 2 であるとき, G 1 H 1, H 2 G 1 H 1, H 3 < を満たすための必要十分条件は (1)H 2 = H 3 (2)H 1 H 2 かつ H 1 H 3 のいずれかを満たすことである. 禁止条件には claw が現れることが多いので,H 1 として claw を考えておくことも重要. より一般に,twin-less( x 1, x 2 s. t. N G x 1 = N G x 2 ) で 考えてみる.
禁止部分グラフ条件の比較 G をグラフとする. V G 上の同値関係 ~ を x~y N G x = N G y に よって定める. C G を ~ に関する同値類とし,B G を C 上のグラフで CC E B G C と C の間に G の辺が存在 を満たすものとする. B G
禁止部分グラフ条件の比較 グラフ G が点推移的であるとは, 任意の x, y V G に対して, ある自己同型写像 φ で φ x = y を満たすものが存在することである.
禁止部分グラフ条件の比較 定理 (Chiba, Fujisawa, F. and Ikarashi, 2017) H 1, H 2, H 3 を位数 3 以上の連結グラフとする. H 1 が twin-less であるとき, G 1 H 1, H 2 G 1 H 1, H 3 < を満たすならば (1)H 2 = H 3 (2)H 1 H 2 かつ H 1 H 3 (3)B H 2 B H 3 が点推移的であり, ある i 2,3 に対して,H i は H 5 i のある 1 点をクリークに置き換えることで得られる. のいずれかとなる.
禁止部分グラフ条件の比較 命題下のグラフ H 2, H 3 について, G 1 claw, H 2 G 1 claw, H 3 = かつ G 1 claw, H 3 G 1 claw, H 2 = H 2 である. 特に, G 1 claw, H 2 G 1 claw, H 3 < を満たす. H 2 H 3
禁止部分グラフ条件の比較 ここまでは有限個の例外のみを誤差として扱ってきた. しかし次の定理のように, グラフのクラスの差が無限であっても, その表記が簡単であれば考えやすい. 定理 (Olariu, 1988) G 1 G 1 K 3 は, 部集合が 3 個以上の完全多部グラフからなる集合と一致する. 上の定理より,K 3 -free グラフに関する命題は, 部集合が 3 個以上の完全多部グラフをチェックするだけで -free グラフの命題に拡張できる.
禁止部分グラフ条件の比較 定理 (Duffus et al., 1981) 2- 連結 claw, N -free グラフはハミルトン閉路を持つ. 定理 (Broesma and Veldman, 1990) 2- 連結 claw, P 6 -free グラフはハミルトン閉路を持つ. 定理 (Bedrossian, 1991) 2- 連結 claw, B 1,2 -free グラフはハミルトン閉路を持つ. 定理 (Faudree et al., 1995) 位数 10 以上の 2- 連結 claw, Z 3 -free グラフは, ハミルトン閉路を持つ.
禁止部分グラフ条件の比較 まず,G 1 claw, B 1,2 G 1 claw, N に注目する. 以下のようなグラフが属するため, これは無限集合である. 例 1. m + 1 4 個の点素なクリーク C, L 1,, L m をとる. ただし C m とする. 2. R 1,, R m を C の点素な部分クリークとする. 3. L i と R i を完全に辺で結ぶ. ( このようなグラフを generalized comb と呼ぶ.) このグラフは claw, B 1,2 -free であるが,N-free でない.
禁止部分グラフ条件の比較 定理 (F. and Tsuchiya, 2015) G 1 claw, B 1,2 G 1 claw, N は,generalized comb からなる集合と一致する. 定理 (Duffus et al., 1981) 2- 連結 claw, N -free グラフはハミルトン閉路を持つ. 上の 2 つの定理の系として,Bedrossian の定理 (2- 連結 claw, B 1,2 -free グラフはハミルトン閉路を持つ ) が得られる.
禁止部分グラフ条件の比較 G を 2- 連結 claw, B 1,2 -free グラフとする. G が N-free であれば,G は 2- 連結 claw, N -free なのでハミルトン閉路を持つ. G が N-free でなければ,G G 1 claw, B 1,2 となるため,generalized comb である. すると,G にハミルトン閉路が見つかる. G 1 claw, N
禁止部分グラフ条件の比較 グラフ G の各頂点を 1 点以上のクリークで置き換えて得られるグラフ全体の集合を A G によって表す. G A G 定理 (Chen, F., Shan, Tsuchiya and Yang, 2017+) G 1 claw, B 1,2 G 1 claw, P 6 = n 6 A P n n 7 A C n
禁止部分グラフ条件の比較 定理 (Chen, F., Shan, Tsuchiya and Yang, 2017+) G 1 claw, B 1,2 G 1 claw, P 6 = n 6 A P n n 7 A C n 定理 (Broesma and Veldman, 1990) 2- 連結 claw, P 6 -free グラフはハミルトン閉路を持つ. 上の 2 つの定理の系としても,Bedrossian の定理 (2- 連結 claw, B 1,2 -free グラフはハミルトン閉路を持つ ) が得られる.
まとめ グラフの性質 P について,P を満たさないグラフの共通構造を禁止すれば,P のための 本質的 な十分条件が得られる. グラフの問題では, 位数が小さいものが例外になりがちなので, 位数十分大という仮定を加えるのが自然だが, それによって対象のクラスが空になることも 性質 P を満たさない共通構造は似たようなものになることがあるため, 実は本質的に等しい (or 包含関係 ) かも? もう一度, 対象のクラスに目を向けましょう! ご清聴ありがとうございました