古谷 倫貴 （北里大学一般教育部）
グラフの禁止構造条件について
1. 禁止部分グラフ a. 問題設定 b. ハミルトン閉路のための禁止部分グラフ c. 完全マッチングのための禁止部分グラフ d. 禁止部分グラフ条件の完全決定の難易 2. 自明な禁止部分グラフ条件 3. 禁止部分グラフ条件の比較 話の流れ
グラフのある性質 𝑃 について，𝑃 のための（十分）条件と して良いものを考えたい． 例えば “完全マッチングを持つ” という性質に着目してみる． ※完全マッチング：グラフの全頂点を用いる独立辺の集合 ※グラフに完全マッチングが存在するための有名な必要 十分があるが，それについてはとりあえず無視する． 問題設定
… 奇数 完全マッチングを持たないグラフとは？ 奇位数グラフは完全マッチングを持たない 下は完全マッチングを持たない偶位数グラフの無限列 このグラフたちには共通して の形が現れている！ （このグラフをclawという。） ➡ 偶位数グラフにclaw の構造を“禁止”すれば，完全 マッチングの存在が言える？ … … … 奇数 𝐾2𝑚−1 𝐾2𝑚−1 … 𝐾2𝑚−1 𝐾2𝑘−1 2𝑘 + 1 問題設定
𝐺 をグラフとする． 𝑆 ⊆ 𝑉 𝐺 について， 𝑢𝑣 ∈ 𝐸 𝐺 ∶ 𝑢, 𝑣 ∈ 𝑆 を辺集合と する 𝑆 上のグラフ 𝐺 𝑆 を，𝑆 で誘導される 𝐺 の誘導部分 グラフという． 𝐺 がグラフ 𝐻 と同型な誘導部分グラフを含むとき，𝐻 ≺ 𝐺 と書く． 𝐻 ⊀ 𝐺 となるとき，𝐺 は 𝐻-free であるという． 注意 ２つのグラフ 𝐻1, 𝐻2 に対して，𝐻1 ≺ 𝐻2 が成り立つとき， 任意の 𝐻1-free グラフは 𝐻2-free である． 特に，𝐻1-free グラフのクラスより，𝐻2-free グラフのクラス の方が大きい． 問題設定
定理 （Sumner, 1974） 偶位数連結 claw-free グラフは完全マッチングを持つ． （証明） ある偶位数連結 claw-free グラフ 𝐺 が完全マッチングを 持たないと仮定する． すると 1-因子定理（Tutte, 1947）より，ある ∅ ≠ 𝑋 ⊆ 𝑉 𝐺 に対して， 𝐺 − 𝑋 の奇位数成分の個数 ≥ 𝑋 + 2 が成り立つ． このような 𝑋 を最小にとると，𝑋 の頂点は 𝐺 − 𝑋 の奇位数 連結成分のうち，少なくとも３個と隣接する． ➡ clawが誘導部分グラフとして見つかり，矛盾する． 問題設定
グラフが “ハミルトン閉路を持つ” という性質について， グラフの禁止条件は？ ※ハミルトン閉路：グラフのすべての頂点を通る閉路 ハミルトン閉路を持つグラフは 2-連結であるから，対象の グラフは 2-連結グラフに限る． 下はハミルトン閉路を持たない 2-連結グラフの無限列 これらの共通の誘導部分グラフは？ ➡ （𝑃3）が最大の共通の連結誘導部分グラフ． … … … … ハミルトン閉路のための禁止部分グラフ
命題 連結 𝑃3-free グラフ 𝐺 は完全グラフである． （証明） 𝐺 が完全グラフでないと仮定すると，ある非隣接な２頂点が 存在する． 𝐺 は連結であるから，距離が 2 となる２頂点 𝑢, 𝑣 が存在 する． このとき，𝑤 ∈ 𝑁𝐺 𝑢 ∩ 𝑁𝐺 𝑣 について，𝑢𝑤𝑣 が誘導 𝑃3 と なる． 命題 2-連結 𝑃3-free グラフはハミルトン閉路を持つ． ハミルトン閉路のための禁止部分グラフ
ℋ をいくつかの連結グラフからなる集合とする． グラフ 𝐺 が， ∀𝐻 ∈ ℋ, 𝐻 ⊀ 𝐺 を満たすとき，𝐺 は ℋ-free であるという． いくつかの連結グラフからなる集合 ℋ1, ℋ2 に対して， ∀𝐻2 ∈ ℋ2, ∃𝐻1 ∈ ℋ1 s. t. 𝐻1 ≺ 𝐻2 が成り立つとき，ℋ1 ≤ ℋ2 と書く． 注意 ℋ1 ≤ ℋ2 ならば 任意の ℋ1-free グラフは ℋ2-free である． ハミルトン閉路のための禁止部分グラフ
定理 （Duffus et al., 1981）
2-連結 claw, 𝑁 -free グラフはハミルトン閉路を持つ．
定理 （Bedrossian, 1991）
2-連結 claw, 𝐵1,2 -free グラフはハミルトン閉路を持つ． 定理 （Broesma and Veldman, 1990）
2-連結 claw, 𝑃6 -free グラフはハミルトン閉路を持つ．
定理 （Bedrossian, 1991） ２つの連結グラフ 𝐻1, 𝐻2 が命題 「2-連結 𝐻1, 𝐻2 -free グラフはハミルトン閉路を持つ」 を満たすための必要十分条件は， （１） 𝐻1, 𝐻2 ≤ claw, 𝑁 （２） 𝐻1, 𝐻2 ≤ claw, 𝑃6 （３） 𝐻1, 𝐻2 ≤ claw, 𝐵1,2 のいずれかとなることである． ハミルトン閉路のための禁止部分グラフ
定理 （Faudree et al., 1995） 2-連結 claw, 𝑍3 -free グラフは，以下の２つを除き ハミルトン閉路を持つ． 「2-連結 claw, 𝑍3 -free グラフはハミルトン閉路を持つ」と いう命題は，反例があるため成り立たない． （よって Bedrossian の特徴付けに claw, 𝑍3 は現れない） しかし，反例が２個しか存在しないことが分かっているため， claw, 𝑍3 はハミルトン閉路のための禁止条件と見なして 良さそう． ハミルトン閉路のための禁止部分グラフ
定理 （Faudree and Gould, 1997） ２つの連結グラフ 𝐻1, 𝐻2 が命題 「位数が十分大きい 2-連結 𝐻1, 𝐻2 -free グラフは ハミルトン閉路を持つ」 を満たすための必要十分条件は， （１） 𝐻1, 𝐻2 ≤ claw, 𝑁 （２） 𝐻1, 𝐻2 ≤ claw, 𝑃6 （３） 𝐻1, 𝐻2 ≤ claw, 𝐵1,2 （４） 𝐻1, 𝐻2 ≤ claw, 𝑍3 のいずれかとなることである． ハミルトン閉路のための禁止部分グラフ 小さい例外グラフを認めて，今後は「位数が十分大きい」と いう仮定の下で問題を考える．
ハミルトン閉路のための禁止部分グラフ
「位数が十分大きい 2-連結 𝐻1, 𝐻2, 𝐻3 -free グラフは
ハミルトン閉路を持つ」
を満たす３つの連結グラフ 𝐻1, 𝐻2, 𝐻3 の特徴付けも 知られており，本質的に12種類に分類される．
ハミルトン閉路のための禁止部分グラフ 禁止するグラフの個数を増やすと，命題は（ある意味で） 強くなる． claw, 𝑍3 ≤ claw, 𝐵1,3, 𝑅 なので， 位数が十分大きい 2-連結 claw, 𝑍3 -free グラフは ハミルトン閉路を持つ（Faudree et al., 1995） が導かれる． 定理 （Brousek, 2002） 位数が十分大きい 2-連結 claw, 𝐵1,3, 𝑅 -free グラフは ハミルトン閉路を持つ．
定理 （Fujisawa, 2012） ２つの連結グラフ 𝐻1, 𝐻2 が命題 「位数が十分大きい 3-連結 𝐻1, 𝐻2 -free グラフは ハミルトン閉路を持つ」 を満たすならば，ある 𝑖 ∈ 1,2 に対して 𝐻𝑖 ≺ 𝐾1,3 かつ （１）𝐻3−𝑖 ≺ 𝑃10 （２）𝐻3−𝑖 は 𝐾3 から３本の点素な道を出した位数12以下の グラフ （３）２つの 𝐾3 を長さ 1,3,5,7 いずれかの道で結んだグラフ のいずれかとなる． ハミルトン閉路のための禁止部分グラフ
予想 （Matthews and Sumner, 1984）
4-連結 claw-free グラフは，ハミルトン閉路を持つ． 定理 （Kaiser and Vrana, 2012）
最小次数 6 以上の 5-連結 claw-free グラフは，ハミルトン 閉路を持つ．
【（この講演での）グラフの禁止条件】 性質 𝑃 に対して，それを見つけるためのグラフの禁止 条件を見つけたい． 性質 𝑃 の自明な十分条件 （完全マッチング：偶位数，ハミルトン閉路：2-連結性） は仮定しておく． ただし，より強い仮定（ハミルトン閉路について 𝑘-連結） を仮定することもある． 対象のグラフは，位数が十分大きいもののみを考える． ※一般に，禁止するグラフの個数を増やすと考えるべき 状況も増えて，強い命題が得られる． ハミルトン閉路のための禁止部分グラフ
定理 （Sumner, 1974）
偶位数連結 claw-free グラフは完全マッチングを持つ．
完全マッチングのための禁止部分グラフ
定理 （Plummer and Saito, 2005） 連結グラフ 𝐻 が命題
「位数が十分大きい偶位数連結 𝐻-free グラフは完全 マッチングを持つ」
を満たすための必要十分条件は，𝐻 ≺ claw となることで ある．
定理 （Fujita et al., 2006） ２つの連結グラフ 𝐻1, 𝐻2 が命題 「位数が十分大きい偶位数連結 𝐻1, 𝐻2 -free グラフは 完全マッチングを持つ」 を満たすための必要十分条件は， 𝐻1, 𝐻2 ≤ claw と なることである． 完全マッチングのための禁止部分グラフ
定理 （Ota et al., 2010） ３つの連結グラフ 𝐻1, 𝐻2, 𝐻3 が命題 「位数が十分大きい偶位数連結 𝐻1, 𝐻2, 𝐻3 -free グラフは 完全マッチングを持つ」 を満たすための必要十分条件は， （１） 𝐻1, 𝐻2, 𝐻3 ≤ 𝐾1,3 𝑝 ≥ 4, 𝑞 ≥ 2 （２） 𝐻1, 𝐻2, 𝐻3 ≤ 𝐾1,𝑝, 𝑌𝑞, 𝑄1,𝑟 𝑝 ≥ 4, 𝑞 ≥ 4, 𝑟 ≥ 3 （３） 𝐻1, 𝐻2, 𝐻3 ≤ 𝐾1,𝑝, 𝑃4, 𝑄2,𝑟 𝑝 ≥ 4, 𝑟 ≥ 3 のいずれかとなることである． 完全マッチングのための禁止部分グラフ 𝐾𝑛 … 𝑘 頂点 𝑄𝑘,𝑛 … 𝑛 頂点 𝑌𝑛
定理 （Ota and Sueiro, 2013） 連結グラフの集合 ℋ が命題 「位数が十分大きい偶位数連結 ℋ-free グラフは完全 マッチングを持つ」 を満たすための必要十分条件は， ℋ ≤ 𝐾1,𝑝, 𝑌𝑞, 𝑊𝑟, 𝑍𝑖,𝑠+ ∶ 0 ≤ 𝑖 ≤ 𝑞 − 2 𝑝 ≥ 4, 𝑞 ≥ 2, 𝑟 ≥ 2, 𝑠 ≥ 3 となることである． 完全マッチングのための禁止部分グラフ … 𝑛 頂点 𝑌𝑛 𝐾𝑛 … 𝑊𝑛 𝐾𝑛 … 𝑚 頂点 𝑍𝑛,𝑚+ 禁止条件の 完全決定
完全マッチングのための禁止部分グラフ
連結度を上げると？
定理 （Sumner, 1975; Plummer and Saito, 2005） 𝑘 ≥ 2 を整数とする． 連結グラフ 𝐻 が命題 「位数が十分大きい偶位数 𝑘-連結 𝐻-free グラフは完全 マッチングを持つ」 を満たすための必要十分条件は，𝐻 ≺ 𝐾1,𝑘+1 となることで ある．
定理 （Fujisawa et al., 2011） 𝑘 ≥ 2 を整数とする． ２つの連結グラフ 𝐻1, 𝐻2 が命題 「位数が十分大きい偶位数 𝑘-連結 𝐻1, 𝐻2 -free グラフは 完全マッチングを持つ」 を満たすための必要十分条件は， （１） 𝐻1, 𝐻2 ≤ 𝐾1,𝑘+1 （２） 𝐻1, 𝐻2 ≤ 𝐾1,𝑘+2, 𝐹𝑝 1 ≤ 𝑝 ≤ 𝑘 2 + 1 のいずれかとなることである． 完全マッチングのための禁止部分グラフ … 𝑛 頂点 𝐹𝑛
完全マッチングのための禁止部分グラフ 連結度の高いグラフにおいては，star を禁止すれば完全 マッチングが存在する． ➡ 禁止する star に対して，連結度を “もっと” 大きくすると， マッチングに関してより強い性質が得られるのでは？ 整数 𝑚 ≥ 0, 𝑛 ≥ 0 に対し，グラフ 𝐺 が 𝐸 𝑚, 𝑛 を満たす とは，辺素な任意の２つのマッチング 𝑀, 𝑁 ⊆ 𝐸 𝐺 𝑀 = 𝑚, 𝑁 = 𝑛 について，𝐺 が 𝑀 ⊆ 𝐹 かつ 𝐹 ∩ 𝑁 = ∅ なる完全マッチング 𝐹 = 𝐹𝑀,𝑁 を持つことである．
完全マッチングのための禁止部分グラフ
定理 （Aldred and Plummer, 1999）
𝑘 ≥ 1, 𝑚 ≥ 0, 𝑛 ≥ 0 を，𝑚 + 𝑛 ≥ 1 かつ 𝑛 ≤ 𝑘−2𝑚+1 2 を 満たす整数とするとき，位数が十分大きい偶位数 𝑘-連結 𝐾𝑘−2𝑚−𝑛+2-free グラフは 𝐸 𝑚, 𝑛 を満たす． 定理 （Egawa and F., 2016） 𝑘 ≥ 4, 𝑚 ≥ 0, 𝑛 ≥ 3 を，𝑘−2𝑚+2 2 ≤ 𝑛 ≤ 𝑘 − 2𝑚 − 1 を 満たす整数とするとき，位数が十分大きい偶位数 𝑘-連結 𝐾 𝑘−𝑚+2 2 -free グラフは 𝐸 𝑚, 𝑛 を満たす． 𝑛 に依存しない 禁止条件
禁止部分グラフ条件の完全決定の難易
グラフの禁止条件が，（自明な必要条件下で）完全決定 している問題
HIST （F. and Tsuchiya, 2013）
※HIST：葉以外の頂点の次数が 3 以上の全域木
0 < 𝑡 < 1 に対する 𝑡-タフ（Ota and Sueiro, 2013） ※𝐺 が 𝑡-タフ ⇔ ∀𝑆 ∶ cutset of 𝐺, 𝑆
# of compo. of 𝐺−𝑆 ≥ 𝑡 全域 2-歩道 （F., 2014）
禁止部分グラフ条件の完全決定の難易
命題 （Jackson and Wormald, 1990） 𝑘 ≥ 2 を整数とする． グラフ 𝐺 が全域 𝑘-歩道を持つならば，𝐺 は 1/𝑘 -タフで ある． また， 1/𝑘 -タフであるが全域 𝑘-歩道を持たないグラフの 無限列が存在する． 一方で，「 1/2 -タフのための禁止条件」と「全域 2-歩道の ための禁止条件」は一致する！ 問題 グラフの２つの（強弱のある）性質について，それらの ための禁止条件が等しいものは他にあるか？
禁止部分グラフ条件の完全決定の難易
グラフの禁止条件として，“ 𝐻1, 𝐻2 -free” の形でも未決定 の問題
𝑘 ≥ 3 に対する全域 𝑘-木 （cf. Ota and Sugiyama, 2010）
※𝑘-木：すべての頂点の次数が 𝑘 以下の木
全域部分 Halin グラフ （cf. Chen et al., 2017+）
※Halin グラフ：HIT の葉を閉路で繋いだ平面グラフ 辺支配閉路 （cf. Chiba, F. and Tsuchiya, 2015, 2016）
※辺支配閉路：取り除くと孤立点のみが残る閉路
問題
グラフの禁止条件を考えるに当たって，簡単・難しいの 違いは何か？
自明な禁止部分グラフ条件 定理 （Fujisawa et al., 2013） 5-連結 claw, 𝐾4 -free グラフは，正二十面体グラフに限る． 特に 「位数 13 以上の 5-連結 claw, 𝐾4 -free グラフのクラス」 は（空なので）どのような性質でも満たす． このようなグラフのクラスを考えることは無駄であるが， 禁止条件を考える上では避けられないので，予め特定して おきたい． 禁止部分グラフを考えるとき，位数が十分大きいことを 仮定するのが通常であった． ➡そこに弊害も…
自明な禁止部分グラフ条件 𝑘 ≥ 1 を整数とする． 𝒢𝑘 を 𝑘-連結グラフ全体からなる集合とする． 連結グラフの集合 ℋ に対して， と定める． -free 𝒢𝑘 ℋ = 𝐺 ∈ 𝒢𝑘 ∶ 𝐺 は ℋ 問題 𝒢𝑘 ℋ < ∞ を満たすような ℋ を決定せよ．
自明な禁止部分グラフ条件 定理 （Diestel） 連結グラフの集合 ℋ が 𝒢1 ℋ < ∞ を満たすための 必要十分条件は， ℋ ≤ 𝐾𝑝, 𝑃𝑞, 𝐾1,𝑟 𝑝 ≥ 1, 𝑞 ≥ 1, 𝑟 ≥ 1 となることである． （必要性の証明） 𝐾1,𝑛 ∶ 𝑛 ≥ 1 は無限集合であるから，ある 𝑟 ≥ 1 に対して 𝐾1,𝑟 は ℋ-free でない． よって，∃𝐻 ∈ ℋ s. t. 𝐻 ≺ 𝐾1,𝑟 となる． したがって，ℋ ≤ 𝐾1,𝑟 となる． 同様に， 𝐾𝑛 ∶ 𝑛 ≥ 1 と 𝑃𝑛 ∶ 𝑛 ≥ 1 を考えれば，ある 𝑝 ≥ 1, 𝑞 ≥ 1 について ℋ ≤ 𝐾𝑝 と ℋ ≤ 𝑃𝑞 となる．
自明な禁止部分グラフ条件 （十分性の証明） 𝐺 を連結 𝐾𝑝, 𝑃𝑞, 𝐾1,𝑟 -free グラフとする． 𝑝 ≤ 2 または 𝑞 ≤ 2 または 𝑟 = 1 だと，𝐺 ≃ 𝐾1 となるので， 𝑝 ≥ 3, 𝑞 ≥ 3, 𝑟 ≥ 2 として良い． 𝐺 は 𝑃𝑞-free なので，diam 𝐺 ≤ 𝑞 − 2． 𝑥 ∈ 𝑉 𝐺 を 𝑑𝐺 𝑥 = Δ 𝐺 を満たす頂点とする． 𝐺 は 𝐾𝑝, 𝐾1,𝑟
-
free なので，𝑁𝐺 𝑥 はサイズ 𝑝 − 1 の クリークも，サイズ 𝑟 の独立集合も含まない． よって Δ 𝐺 = 𝑑𝐺 𝑥 ≤ 𝑅 𝑝 − 1, 𝑟 （𝑅 ∗,∗ ：ラムゼー数）． 以上より 𝑉 𝐺 ≤ Δ 𝐺 diam 𝐺 ≤ 𝑅 𝑝 − 1, 𝑟 − 1 𝑞−2．自明な禁止部分グラフ条件 連結度を上げると？ 命題 （Fujisawa et al., 2013） 𝑘 ≥ 1 を整数とする． 連結グラフ 𝐻 が 𝒢𝑘 𝐻 < ∞ を満たすための必要十分 条件は，𝐻 ≺ 𝐾2 となることである．
自明な禁止部分グラフ条件 命題 （Fujisawa et al., 2013） 𝑘 ≥ 1 を整数とする． 連結グラフ 𝐻1, 𝐻2 が 𝒢𝑘 𝐻1, 𝐻2 < ∞ を満たすならば， ∃𝑝 ≥ 3, 2 ≤ ∃𝑟 ≤ 𝑘 𝑠. 𝑡. 𝐻1, 𝐻2 ≤ 𝐾𝑝, 𝐾1,𝑟 となる． 定理 （Fujisawa et al., 2013） 1 ≤ 𝑘 ≤ 6 を整数とする． 連結グラフ 𝐻1, 𝐻2 が 𝒢𝑘 𝐻1, 𝐻2 < ∞ を満たすための 必要十分条件は， （１） 𝐻1, 𝐻2 ≤ 𝐾𝑝, 𝐾1,2 𝑝 ≥ 3 （２） 𝐻1, 𝐻2 ≤ 𝐾3, 𝐾1,𝑟 3 ≤ 𝑟 ≤ 𝑘 if 3 ≤ 𝑘 ≤ 6 （３） 𝐻1, 𝐻2 ≤ 𝐾4, 𝐾1,3 if 5 ≤ 𝑘 ≤ 6 のいずれかとなることである．
自明な禁止部分グラフ条件 定理 （F. and Okubo, 2015） 連結グラフ 𝐻1, … , 𝐻4 が 𝒢2 𝐻1, … , 𝐻4 < ∞ を満たす ための必要十分条件は以下のいずれかとなることである． （１） 𝐻1, … , 𝐻4 ≤ 𝐾3, 𝑃5, 𝐾2,𝑟 𝑟 ≥ 2 （２） 𝐻1, … , 𝐻4 ≤ 𝐾3, 𝑃6, 𝐾2,2 （３） 𝐻1, … , 𝐻4 ≤ 𝐾3, 𝑃6, 𝐾2,𝑟, 𝐻𝑠1 𝑟 ≥ 3, 𝑠 ≥ 2 （４） 𝐻1, … , 𝐻4 ≤ 𝐾3, 𝑃7, 𝐾2,2, 𝐻𝑠2 𝑠 ≥ 2 （５） 𝐻1, … , 𝐻4 ≤ 𝐾3, 𝑃𝑞, 𝐾2,2, 𝐻𝑠3 𝑞 ≥ 8, 𝑠 ≥ 3 （６） 𝐻1, … , 𝐻4 ≤ 𝐾3, 𝑃𝑞, 𝐾2,𝑟, 𝐻𝑠4 𝑞 ≥ 7, 𝑟 ≥ 2, 𝑠 ≥ 3, 𝑞, 𝑟 ≠ 7,2 （７） 𝐻1, … , 𝐻4 ≤ 𝐾𝑝, 𝑃5, 𝐾2,𝑟, 𝐻𝑠5 𝑝 ≥ 4, 𝑟 ≥ 2, 𝑠 ≥ 2 （８） 𝐻1, … , 𝐻4 ≤ 𝐾𝑝, 𝑃6, 𝐾2,2, 𝐻𝑠5 𝑝 ≥ 4, 𝑠 ≥ 2
自明な禁止部分グラフ条件 … 𝐻𝑛1 … 𝐻𝑛2 … 𝐻𝑛3 … 𝐻𝑛4 … 𝐻𝑛5 大抵の場合は禁止するグラフを制限するので，当初の目的 のためにはこの位調べておけば十分．
自明な禁止部分グラフ条件
𝒢3 𝐻1, 𝐻2, 𝐻3 < ∞ について
（Egawa and F., 2014; Egawa et al., 2015）
禁止部分グラフ条件の比較 連結グラフの２つの集合 ℋ1, ℋ2 について， “ほとんど” 𝒢𝑘 ℋ1 ⊆ 𝒢𝑘 ℋ2 “ほとんど” 𝒢𝑘 ℋ1 = 𝒢𝑘 ℋ2 などが分かれば，禁止条件の問題について，一方の情報 が他方に知見を与える． ℋ1 ≤ ℋ2 であれば，𝒢𝑘 ℋ1 ⊆ 𝒢𝑘 ℋ2 であったが，それ 以外の状況でも（ほとんど） 𝒢𝑘 ℋ1 ⊆ 𝒢𝑘 ℋ2 が成り立つ ことはあるか？ 問題 𝒢𝑘 ℋ1 − 𝒢𝑘 ℋ2 < ∞ や 𝒢𝑘 ℋ1 △ 𝒢𝑘 ℋ2 < ∞ を 満たすような ℋ1, ℋ2 を決定せよ．
禁止部分グラフ条件の比較 𝒢1 𝐻1 − 𝒢1 𝐻2 < ∞ かつ 𝐻1 ⊀ 𝐻2 を満たす 𝐻1, 𝐻2 は 存在するか？ 命題 下のグラフ 𝐻1, 𝐻2 について， 𝒢1 𝐻1 − 𝒢1 𝐻2 < ∞ かつ 𝐻1 ⊀ 𝐻2 を満たす． rep. 十分大のトーラス上 6正則三角形分割 𝐻1 𝐻2 （証明） 𝐻1 ⊀ 𝐻2 は自明． 𝒢1 𝐻1 − 𝒢1 𝐻2 = 𝐻2 ，すなわち 𝐻2 を誘導部分グラフ に持つ連結 𝐻1-free グラフは 𝐻2 のみを示せば良い．
禁止部分グラフ条件の比較 𝒢1 𝐻1 − 𝒢1 𝐻2 < ∞ かつ 𝐻1 ⊀ 𝐻2 を満たす 𝐻1, 𝐻2 の 特徴付けは難しそう… 定理 （Fujita et al., 2013） 連結グラフ 𝐻1, 𝐻2 が 𝒢1 𝐻1 − 𝒢1 𝐻2 < ∞ かつ を満たすならば，以下が成り立つ． （１）𝛿 𝐻1 = 1, Δ 𝐻1 = 𝑉 𝐻1 − 1 （２）∃𝑎1, ∃𝑎2 ∈ 𝑉 𝐻1 s. t. 𝑁𝐺 𝑎1 = 𝑁𝐺 𝑎2 （３）∃𝑏1, ∃𝑏2 ∈ 𝑉 𝐻1 s. t. 𝑁𝐺 𝑏1 = 𝑁𝐺 𝑏2 （４） 𝑉 𝐻2 ≥ 2 𝑉 𝐻1 − 3 （５）𝛿 𝐻2 ≥ 𝑉 𝐻1 − 2 𝐻1 ⊀ 𝐻2
禁止部分グラフ条件の比較 𝒢1 𝐻1 △ 𝒢1 𝐻2 < ∞ を満たす 𝐻1, 𝐻2 は？ 定理 （Fujita et al., 2013） 位数 3 以上の連結グラフ 𝐻1, 𝐻2 が を満たすための必要十分条件は 𝐻1 = 𝐻2 となることである． （必要性の証明） 背理法と対称性より 𝐻1 ⊀ 𝐻2 と仮定する． 𝐻1 = 𝑃3 と仮定すると，𝒢1 𝐻1 = 𝐾𝑛 ∶ 𝑛 ≥ 1 となる． 𝐻1 ⊀ 𝐻2，すなわち 𝐻2 は 𝐻1-free であるから，𝐻2 は完全 グラフである． このとき， 𝐾𝑛 ∶ 𝑛 ≥ 𝑉 𝐻2 ⊆ 𝒢1 𝐻1 − 𝒢1 𝐻2 となり， 𝒢1 𝐻1 − 𝒢1 𝐻2 < ∞ に反する． よって 𝐻1 ≠ 𝑃3 である． 𝒢1 𝐻1 △ 𝒢1 𝐻2 < ∞
禁止部分グラフ条件の比較 𝒜1 = ∶ 𝑛 ≥ 1 は 𝐻2-free でない連結グラフの 無限集合であるから，𝒜1 ⊆ 𝒢1 − 𝒢1 𝐻2 を満たす． 𝒢1 𝐻1 − 𝒢1 𝐻2 < ∞ であるから， ∃𝑛1 ≥ 1, ∃𝐻2′ ≺ 𝐻2 s. t. 𝐻1 = となる． 𝒜2 = ∶ 𝑛 ≥ 1 について同様に考えると， ∃𝑛2 ≥ 1, ∃𝐻2′′ ≺ 𝐻2 s. t. 𝐻1 = となる． 特に Δ 𝐻1 = 𝑉 𝐻1 − 1, 𝛿 𝐻1 = 1 となる． また，𝒜2 の 𝑃𝑛 の根本の選び方より，𝛿 𝐻2 ≥ 𝑉 𝐻1 − 2． 𝐻2 … 𝑃𝑛 𝐻2′′ … 𝑃𝑛2 𝐻2 𝐾𝑛 𝐻2′ 𝐾𝑛1
禁止部分グラフ条件の比較 以上より，以下のようになる． よって， 𝑉 𝐻2 − 𝑁𝐻2 𝑥 ≥ 𝑉 𝐻1 − 2 となる． したがって， 𝑉 𝐻2 = 𝛿 𝐻2 + 1 + 𝑉 𝐻2 − 𝑁𝐻2 𝑥 ≥ 2 𝑉 𝐻1 − 3. 𝑉 𝐻2 > 𝑉 𝐻1 であれば 𝐻2 ⊀ 𝐻1 なので，同じ議論 により 𝑉 𝐻1 ≥ 2 𝑉 𝐻2 − 3 が得られて矛盾． 𝑉 𝐻2 ≤ 𝑉 𝐻1 であれば 𝑉 𝐻1 = 𝑉 𝐻2 = 3 と なり，𝐻1 ⊀ 𝐻2 より 𝐻1, 𝐻2 = 𝑃3, 𝐾3 となって，最初 の議論で矛盾． 𝑥 𝐻2′ 𝑑𝐻1 𝑥 = 1 𝐻1 =
禁止部分グラフ条件の比較 定理 （Fujita et al., 2013） 𝑘 ≥ 1 を整数とする． 位数 3 以上の連結グラフ 𝐻1, 𝐻2 が を満たすための必要十分条件は 𝐻1 = 𝐻2 となることである． 𝒢𝑘 𝐻1 △ 𝒢𝑘 𝐻2 < ∞ 定理 （Fujita et al., 2013） 連結グラフ 𝐻 と ℋ ≤ 3 なる連結グラフの集合 ℋ が 𝒢1 𝐻 △ 𝒢1 ℋ < ∞ を満たすならば， （１）𝐻 ∈ ℋ （２）𝐻 = 𝐾3 かつ ℋ = 3 のいずれかとなる． ※ 𝒢1 𝐾3 △ 𝒢1 𝐾4, , < ∞ 𝒢1 𝐾3 △ 𝒢1 𝐾5, , < ∞
禁止部分グラフ条件の比較 ここで， 𝒢1 𝐾3 △ 𝒢1 𝐾4, , < ∞ という事実に着目 する． この右側は，𝐾3 に１頂点を加えて適当な辺を加えた集合で ある． 一般に，連結グラフ 𝐻 に対して，𝐻 に１頂点 𝑥 を加え， 𝑥 と 𝐻 を１本以上の辺で結んで得られるグラフの集合を ℋ𝐻+ と表す． 注意 連結グラフ 𝐻 に対して，𝒢1 𝐻 △ 𝒢1 ℋ𝐻+ = 𝐻 となる．
禁止部分グラフ条件の比較
グラフの禁止条件で重要な，claw に注目する． 注意
ℋclaw+ = ．
禁止部分グラフ条件の比較 定理 （F. and Yokota, 2017+） 整数 𝑘 ≥ 1 と ℋ ⊆ ℋclaw+ が 𝒢𝑘 claw △ 𝒢𝑘 ℋ < ∞ を 満たすための必要十分条件は以下のいずれかとなること である． （１）𝑘 = 1 かつ， 𝐻1, … , 𝐻6 ⊆ ℋ （２）𝑘 = 2 かつ， 𝐻1, … , 𝐻6 ⊆ ℋ または 𝐻1, … , 𝐻4, 𝐻7 ⊆ ℋ （３）𝑘 = 3 かつ， 𝐻1, … , 𝐻5 ⊆ ℋ または 𝐻1, … , 𝐻4, 𝐻7 ⊆ ℋ （４）𝑘 ≥ 4 かつ， 𝐻1, 𝐻2, 𝐻5, 𝐻6 ⊆ ℋ または 𝐻1, 𝐻2, 𝐻3, 𝐻6, 𝐻7 ⊆ ℋ または 𝐻1, … , 𝐻5 ⊆ ℋ または 𝐻1, … , 𝐻4, 𝐻7 ⊆ ℋ
禁止部分グラフ条件の比較 定理 （F. and Yokota, 2017+） Matthews-Sumner 予想は，以下と同値である． （１）4-連結 𝐻1, 𝐻2, 𝐻5, 𝐻6 -free グラフはハミルトン閉路を 持つ． （２）4-連結 𝐻1, 𝐻2, 𝐻3, 𝐻6, 𝐻7 -free グラフはハミルトン 閉路を持つ． （３）4-連結 𝐻1, … , 𝐻5 -free グラフはハミルトン閉路を 持つ． （４）4-連結 𝐻1, … , 𝐻4, 𝐻7 -free グラフはハミルトン閉路を 持つ．
予想 （Matthews and Sumner, 1984）
禁止部分グラフ条件の比較
定理 （Chiba, Fujisawa, F. and Ikarashi, 2017） 𝐻1, 𝐻2, 𝐻3 を位数 3 以上の連結グラフとする． 𝛿 𝐻1 ≥ 2 であるとき， 𝒢1 𝐻1, 𝐻2 △ 𝒢1 𝐻1, 𝐻3 < ∞ を 満たすための必要十分条件は （１）𝐻2 = 𝐻3 （２）𝐻1 ≺ 𝐻2 かつ 𝐻1 ≺ 𝐻3 のいずれかを満たすことである． 禁止条件には claw が現れることが多いので，𝐻1 として claw を考えておくことも重要． より一般に，twin-less（∄𝑥1, ∄𝑥2 𝑠. 𝑡. 𝑁𝐺 𝑥1 = 𝑁𝐺 𝑥2 ）で 考えてみる．
禁止部分グラフ条件の比較 𝐺 をグラフとする． 𝑉 𝐺 上の同値関係 ~ を 「𝑥~𝑦 ⟺ 𝑁𝐺 𝑥 = 𝑁𝐺 𝑦 」 に よって定める． 𝒞𝐺 を ~ に関する同値類とし，𝐵 𝐺 を 𝒞 上のグラフで 𝐶𝐶′ ∈ 𝐸 𝐵 𝐺 ⟺ 𝐶 と 𝐶′ の間に 𝐺 の辺が存在 を満たすものとする． 𝐵 𝐺
禁止部分グラフ条件の比較
グラフ 𝐺 が点推移的であるとは，任意の 𝑥, 𝑦 ∈ 𝑉 𝐺 に
対して，ある自己同型写像 𝜙 で 𝜙 𝑥 = 𝑦 を満たすものが 存在することである．
禁止部分グラフ条件の比較
定理 （Chiba, Fujisawa, F. and Ikarashi, 2017） 𝐻1, 𝐻2, 𝐻3 を位数 3 以上の連結グラフとする． 𝐻1 が twin-less であるとき， 𝒢1 𝐻1, 𝐻2 △ 𝒢1 𝐻1, 𝐻3 < ∞ を満たすならば （１）𝐻2 = 𝐻3 （２）𝐻1 ≺ 𝐻2 かつ 𝐻1 ≺ 𝐻3 （３）𝐵 𝐻2 ≃ 𝐵 𝐻3 が点推移的であり，ある 𝑖 ∈ 2,3 に 対して，𝐻𝑖 は 𝐻5−𝑖 のある１点をクリークに置き換える ことで得られる． のいずれかとなる．
禁止部分グラフ条件の比較 命題 下のグラフ 𝐻2, 𝐻3 について， 𝒢1 claw, 𝐻2 − 𝒢1 claw, 𝐻3 = ∅ かつ 𝒢1 claw, 𝐻3 − 𝒢1 claw, 𝐻2 = 𝐻2 である． 特に， 𝒢1 claw, 𝐻2 △ 𝒢1 claw, 𝐻3 < ∞ を満たす． 𝐻2 𝐻3
禁止部分グラフ条件の比較 ここまでは有限個の例外のみを誤差として扱ってきた． しかし次の定理のように，グラフのクラスの差が無限で あっても，その表記が簡単であれば考えやすい． 定理 （Olariu, 1988） 𝒢1 − 𝒢1 𝐾3 は，部集合が 3 個以上の完全多部 グラフからなる集合と一致する． 上の定理より，𝐾3-free グラフに関する命題は，部集合が 3 個以上の完全多部グラフをチェックするだけで -free グラフの命題に拡張できる．
禁止部分グラフ条件の比較
定理 （Duffus et al., 1981）
2-連結 claw, 𝑁 -free グラフはハミルトン閉路を持つ．
定理 （Bedrossian, 1991）
2-連結 claw, 𝐵1,2 -free グラフはハミルトン閉路を持つ． 定理 （Broesma and Veldman, 1990）
2-連結 claw, 𝑃6 -free グラフはハミルトン閉路を持つ．
定理 （Faudree et al., 1995）
位数 10 以上の 2-連結 claw, 𝑍3 -free グラフは， ハミルトン閉路を持つ．
禁止部分グラフ条件の比較
まず，𝒢1 claw, 𝐵1,2 − 𝒢1 claw, 𝑁 に注目する．
以下のようなグラフが属するため，これは無限集合である． 例
（このようなグラフを generalized comb と呼ぶ．）
➡ このグラフは claw, 𝐵1,2 -free であるが，𝑁-free でない． 1. 𝑚 + 1 ≥ 4 個の点素なクリーク 𝐶, 𝐿1, … , 𝐿𝑚 をとる． ただし 𝐶 ≥ 𝑚 とする． 2. 𝑅1, … , 𝑅𝑚 を 𝐶 の点素な部分 クリークとする． 3. 𝐿𝑖 と 𝑅𝑖 を完全に辺で結ぶ． …
禁止部分グラフ条件の比較
定理 （F. and Tsuchiya, 2015）
𝒢1 claw, 𝐵1,2 − 𝒢1 claw, 𝑁 は，generalized comb から なる集合と一致する．
定理 （Duffus et al., 1981）
2-連結 claw, 𝑁 -free グラフはハミルトン閉路を持つ． 上の２つの定理の系として，Bedrossian の定理（2-連結
禁止部分グラフ条件の比較
𝐺 を 2-連結 claw, 𝐵1,2 -free グラフとする．
𝐺 が 𝑁-free であれば，𝐺 は 2-連結 claw, 𝑁 -free なので ハミルトン閉路を持つ．
𝐺 が 𝑁-free でなければ，𝐺 ∈ 𝒢1 claw, 𝐵1,2 − 𝒢1 claw, 𝑁 となるため，generalized comb である．
すると，𝐺 にハミルトン閉路が見つかる．
禁止部分グラフ条件の比較
定理 （Chen, F., Shan, Tsuchiya and Yang, 2017+） 𝒢1 claw, 𝐵1,2 − 𝒢1 claw, 𝑃6 グラフ 𝐺 の各頂点を１点以上のクリークで置き換えて 得られるグラフ全体の集合を 𝒜 𝐺 によって表す． 𝐺 ∈ 𝒜 𝐺 = 𝑛≥6 𝒜 𝑃𝑛 ∪ 𝑛≥7 𝒜 𝐶𝑛
禁止部分グラフ条件の比較
定理 （Broesma and Veldman, 1990）
2-連結 claw, 𝑃6 -free グラフはハミルトン閉路を持つ． 上の２つの定理の系としても，Bedrossian の定理（2-連結
claw, 𝐵1,2 -free グラフはハミルトン閉路を持つ）が得られる． 定理 （Chen, F., Shan, Tsuchiya and Yang, 2017+）
𝒢1 claw, 𝐵1,2 − 𝒢1 claw, 𝑃6 = 𝑛≥6 𝒜 𝑃𝑛 ∪ 𝑛≥7 𝒜 𝐶𝑛
まとめ グラフの性質 𝑃 について，𝑃 を満たさないグラフの共通 構造を禁止すれば，𝑃 のための“本質的”な十分条件が 得られる． グラフの問題では，位数が小さいものが例外になりがち なので，位数十分大という仮定を加えるのが自然だが， それによって対象のクラスが空になることも… 性質 𝑃 を満たさない共通構造は似たようなものになる ことがあるため，実は本質的に等しい（or 包含関係） かも？ ➡ もう一度，対象のクラスに目を向けましょう！ ご清聴ありがとうございました
