閉曲面上のグラフとグラフ彩色 大阪組合せ論セミナー 共同研究 松本直己　成蹊大学 朝山芳弘　 横浜国立大学大学院環境情報学府.

Presentation on theme: "閉曲面上のグラフとグラフ彩色 大阪組合せ論セミナー 共同研究 松本直己　成蹊大学 朝山芳弘　 横浜国立大学大学院環境情報学府."— Presentation transcript:

1 閉曲面上のグラフとグラフ彩色 大阪組合せ論セミナー 共同研究 松本直己　成蹊大学 朝山芳弘　 横浜国立大学大学院環境情報学府

2 Contents 閉曲面上のグラフと彩色について polychromatic coloring について
dynamic coloring について 様々な種類のグラフ彩色

3 位相幾何学的グラフ理論とは グラフ理論 位相幾何学的 グラフ理論 平面グラフでない 平面グラフ 平面三角形分割 平面グラフ
頂点と辺の集合からなる組合せ的な構造であるグラフの構造や特徴を研究する学問分野 位相幾何学的 グラフ理論 特に閉曲面上に辺の交差なく描かれたグラフの構造や特徴を研究する学問分野 どのようなグラフも三次元上で描けてしまうので， 扱う多様体は閉曲面に限定する 平面グラフでない 平面グラフ 平面三角形分割 平面グラフ 各面の境界が 長さ3の閉路である

4 定義 写像 𝑐:𝑉 𝐺 →{1,⋯,𝑘} が𝑘-彩色 𝑑𝑒𝑓 c 𝑢 ≠𝑐(𝑣) for ∀𝑢𝑣∈𝐸(𝐺) 染色数が4のグラフ
またグラフがもつ 𝑘- 彩色の最小値を染色数という 𝐺=(𝑉,𝐸) の 𝑘-彩色 𝑐とは、 写像 𝑐 :𝑉→{1,⋯,𝑘} で どの隣接する2頂点 𝑢,𝑣 に対しても𝑐 𝑢 ≠𝑐(𝑣) が成り立つものである 染色数が4のグラフ (3-彩色を持たない)

5 四色定理について 平面グラフを，隣接する頂点が異なるように，頂 点を塗り分けるには四色あれば十分である．
(任意の平面グラフは4-彩色をもつ) 四色定理 (Appel, Haken ‘76) 閉曲面上に描かれたグラフの彩色を考えるとき， 三角形分割は，頂点数に対して辺の数が極大であるため，三角形分割に限定して考えればよい

6 6色定理 任意の平面グラフは6-彩色をもつ 6色定理 𝑣∈𝑉 (6− deg 𝐺 𝑣 ) ≤12 が成立 証明) 𝑉 𝐺 =n とする
n≤6 は自明． n≥7 で成立することを示す 𝑉 𝐺 ≤𝑛−1 のグラフは6-彩色をもつとする 𝑉 𝐺 −𝐸 𝐺 +𝐹 𝐺 =2 （オイラーの多面体公式）と 2𝐸 𝐺 ≥3𝐹 𝐺 （面と辺数の関係式）から 𝑣∈𝑉 (6− deg 𝐺 𝑣 ) ≤12　が成立 ⇒平面グラフには次数5以下の頂点 𝑣 が存在する 「四色定理」の拡張として ・「平面」を「ほかの閉曲面」に替えた場合の必要な色数の考察 ・より色数が抑えられるグラフクラス(条件)の発見(girthなど) ・彩色を拡張した概念に置き換えた場合の必要な色数の考察(List coloring, Game coloring) ・彩色に条件を課した場合の必要な色数の考察(dynamic coloring, distinguishing coloring, polychromatic coloring)

7 6色定理 任意の平面グラフは6-彩色をもつ 6色定理 𝑣∈𝑉 (6− deg 𝐺 𝑣 ) ≤12 が成立 証明) 𝑉 𝐺 =n とする
n≤6 は自明． n≥7 で成立することを示す 𝑉 𝐺 ≤𝑛−1 のグラフは6-彩色をもつとする 𝑉 𝐺 −𝐸 𝐺 +𝐹 𝐺 =2 （オイラーの多面体公式）と 2𝐸 𝐺 ≥3𝐹 𝐺 （面と辺数の関係式）から 𝑣∈𝑉 (6− deg 𝐺 𝑣 ) ≤12　が成立 ⇒平面グラフには次数5以下の頂点 𝑣 が存在する 「四色定理」の拡張として ・「平面」を「ほかの閉曲面」に替えた場合の必要な色数の考察 ・より色数が抑えられるグラフクラス(条件)の発見(girthなど) ・彩色を拡張した概念に置き換えた場合の必要な色数の考察(List coloring, Game coloring) ・彩色に条件を課した場合の必要な色数の考察(dynamic coloring, distinguishing coloring, polychromatic coloring)

8 6色定理 任意の平面グラフは6-彩色をもつ 6色定理 𝑣∈𝑉 (6− deg 𝐺 𝑣 ) ≤12 が成立 証明) 𝑉 𝐺 =n とする
n≤6 は自明． n≥7 で成立することを示す 𝑉 𝐺 ≤𝑛−1 のグラフは6-彩色をもつとする 𝑉 𝐺 −𝐸 𝐺 +𝐹 𝐺 =2 （オイラーの多面体公式）と 2𝐸 𝐺 ≥3𝐹 𝐺 （面と辺数の関係式）から 𝑣∈𝑉 (6− deg 𝐺 𝑣 ) ≤12　が成立 ⇒平面グラフには次数5以下の頂点 𝑣 が存在する 「四色定理」の拡張として ・「平面」を「ほかの閉曲面」に替えた場合の必要な色数の考察 ・より色数が抑えられるグラフクラス(条件)の発見(girthなど) ・彩色を拡張した概念に置き換えた場合の必要な色数の考察(List coloring, Game coloring) ・彩色に条件を課した場合の必要な色数の考察(dynamic coloring, distinguishing coloring, polychromatic coloring)

9 6色定理 任意の平面グラフは6-彩色をもつ 6色定理 𝑣 𝑣∈𝑉 (6− deg 𝐺 𝑣 ) ≤12 が成立 証明) 𝑉 𝐺 =n とする
n≤6 は自明． n≥7 で成立することを示す 𝑉 𝐺 ≤𝑛−1 のグラフは6-彩色をもつとする 𝑉 𝐺 −𝐸 𝐺 +𝐹 𝐺 =2 （オイラーの多面体公式）と 2𝐸 𝐺 ≥3𝐹 𝐺 （面と辺数の関係式）から 𝑣∈𝑉 (6− deg 𝐺 𝑣 ) ≤12　が成立 ⇒平面グラフには次数5以下の頂点 𝑣 が存在する 𝑣 「四色定理」の拡張として ・「平面」を「ほかの閉曲面」に替えた場合の必要な色数の考察 ・より色数が抑えられるグラフクラス(条件)の発見(girthなど) ・彩色を拡張した概念に置き換えた場合の必要な色数の考察(List coloring, Game coloring) ・彩色に条件を課した場合の必要な色数の考察(dynamic coloring, distinguishing coloring, polychromatic coloring)

10 6色定理 任意の平面グラフは6-彩色をもつ 6色定理 𝑣 つづき) 𝐺−𝑣 のグラフは頂点数が 𝑛−1なので 𝐺−𝑣 は6-彩色をもつ
つづき) 𝐺−𝑣 のグラフは頂点数が 𝑛−1なので 𝐺−𝑣 は6-彩色をもつ 𝑣 の近傍にたかだか5色しか現れないため， 𝐺 の6-彩色が得られる ■ 1 2 𝑣 ＊平面グラフの6-degenerate性は 平面グラフの彩色の良い評価とはなりえないが， 一般の閉曲面では最良の評価を与える(Heawood数) ただし 「四色定理」の拡張として ・「平面」を「ほかの閉曲面」に替えた場合の必要な色数の考察 ・より色数が抑えられるグラフクラス(条件)の発見(girthなど) ・彩色を拡張した概念に置き換えた場合の必要な色数の考察(List coloring, Game coloring) ・彩色に条件を課した場合の必要な色数の考察(dynamic coloring, distinguishing coloring, polychromatic coloring) 3 グラフ𝐺:𝑘-degenerate ⇔𝐺の任意の部分グラフは次数𝑘以下の頂点をもつ 5 4 ＊平面グラフの6-degenerate性は 平面グラフの彩色の良い評価とはなりえないが， 一般の閉曲面では結果として最良の評価を与える

11 6色定理 任意の平面グラフは6-彩色をもつ 6色定理 𝑣 つづき) 𝐺−𝑣 のグラフは頂点数が 𝑛−1なので 𝐺−𝑣 は6-彩色をもつ
つづき) 𝐺−𝑣 のグラフは頂点数が 𝑛−1なので 𝐺−𝑣 は6-彩色をもつ 𝑣 の近傍にたかだか5色しか現れないため， 𝐺 の6-彩色が得られる ■ 1 2 𝑣 ＊平面グラフの6-degenerate性は 平面グラフの彩色の良い評価とはなりえないが， 一般の閉曲面では最良の評価を与える(Heawood数) ただし 「四色定理」の拡張として ・「平面」を「ほかの閉曲面」に替えた場合の必要な色数の考察 ・より色数が抑えられるグラフクラス(条件)の発見(girthなど) ・彩色を拡張した概念に置き換えた場合の必要な色数の考察(List coloring, Game coloring) ・彩色に条件を課した場合の必要な色数の考察(dynamic coloring, distinguishing coloring, polychromatic coloring) 3 グラフ𝐺:𝑘-degenerate ⇔𝐺の任意の部分グラフは次数𝑘以下の頂点をもつ 5 4 ＊平面グラフの6-degenerate性は 平面グラフの彩色の良い評価とはなりえないが， 一般の閉曲面では結果として最良の評価を与える

12 5色定理 任意の平面グラフは5-彩色をもつ 5色定理 𝑣 証明) 𝐺−𝑣 は5-彩色をもち，𝑣 の近傍に5色現れる
証明)　𝐺−𝑣 は5-彩色をもち，𝑣 の近傍に5色現れる 𝑣 の近傍の「1」を「３」に塗り替えられるか検討する ⇒「３」の近傍に「1」が現れているとき 「1」と「3」が交互に現れる (1,3)-Kempe鎖の 「1」と「3」を置換 ⇒(1,3)-Kempe鎖が 𝑣 の近傍に接続しているとき 1 𝑣 2 「四色定理」の拡張として ・「平面」を「ほかの閉曲面」に替えた場合の必要な色数の考察 ・より色数が抑えられるグラフクラス(条件)の発見(girthなど) ・彩色を拡張した概念に置き換えた場合の必要な色数の考察(List coloring, Game coloring) ・彩色に条件を課した場合の必要な色数の考察(dynamic coloring, distinguishing coloring, polychromatic coloring) 5 3 (Jordan の閉曲線定理) 平面内の単純閉曲線は平面をその内部と外部に分離する． 4 (1,3)-Kempe鎖は平面をその内部と外部に分離する 𝑣 の近傍の「２」からのびる(２,４)-Kempe鎖は置換可能

13 5色定理 任意の平面グラフは5-彩色をもつ 5色定理 𝑣 証明) 𝐺−𝑣 は5-彩色をもち，𝑣 の近傍に5色現れる
証明)　𝐺−𝑣 は5-彩色をもち，𝑣 の近傍に5色現れる 𝑣 の近傍の「1」を「３」に塗り替えられるか検討する ⇒「３」の近傍に「1」が現れているとき 「1」と「3」が交互に現れる (1,3)-Kempe鎖の 「1」と「3」を置換 ⇒(1,3)-Kempe鎖が 𝑣 の近傍に接続しているとき 1 𝑣 2 「四色定理」の拡張として ・「平面」を「ほかの閉曲面」に替えた場合の必要な色数の考察 ・より色数が抑えられるグラフクラス(条件)の発見(girthなど) ・彩色を拡張した概念に置き換えた場合の必要な色数の考察(List coloring, Game coloring) ・彩色に条件を課した場合の必要な色数の考察(dynamic coloring, distinguishing coloring, polychromatic coloring) 5 3 (Jordan の閉曲線定理) 平面内の単純閉曲線は平面をその内部と外部に分離する． 4 (1,3)-Kempe鎖は平面をその内部と外部に分離する 𝑣 の近傍の「２」からのびる(２,４)-Kempe鎖は置換可能

14 5色定理 任意の平面グラフは5-彩色をもつ 5色定理 𝑣 証明) 𝐺−𝑣 は5-彩色をもち，𝑣 の近傍に5色現れる
証明)　𝐺−𝑣 は5-彩色をもち，𝑣 の近傍に5色現れる 𝑣 の近傍の「1」を「３」に塗り替えられるか検討する ⇒「３」の近傍に「1」が現れているとき 「1」と「3」が交互に現れる (1,3)-Kempe鎖の 「1」と「3」を置換 ⇒(1,3)-Kempe鎖が 𝑣 の近傍に接続しているとき 1 𝑣 2 「四色定理」の拡張として ・「平面」を「ほかの閉曲面」に替えた場合の必要な色数の考察 ・より色数が抑えられるグラフクラス(条件)の発見(girthなど) ・彩色を拡張した概念に置き換えた場合の必要な色数の考察(List coloring, Game coloring) ・彩色に条件を課した場合の必要な色数の考察(dynamic coloring, distinguishing coloring, polychromatic coloring) 5 3→1 1→3 (Jordan の閉曲線定理) 平面内の単純閉曲線は平面をその内部と外部に分離する． 4 (1,3)-Kempe鎖は平面をその内部と外部に分離する 𝑣 の近傍の「２」からのびる(２,４)-Kempe鎖は置換可能

15 5色定理 任意の平面グラフは5-彩色をもつ 5色定理 𝑣 証明) 𝐺−𝑣 は5-彩色をもち，𝑣 の近傍に5色現れる
証明)　𝐺−𝑣 は5-彩色をもち，𝑣 の近傍に5色現れる 𝑣 の近傍の「1」を「３」に塗り替えられるか検討する ⇒「３」の近傍に「1」が現れているとき 「1」と「3」が交互に現れる (1,3)-Kempe鎖の 「1」と「3」を置換 ⇒(1,3)-Kempe鎖が 𝑣 の近傍に接続しているとき 1 𝑣 2 「四色定理」の拡張として ・「平面」を「ほかの閉曲面」に替えた場合の必要な色数の考察 ・より色数が抑えられるグラフクラス(条件)の発見(girthなど) ・彩色を拡張した概念に置き換えた場合の必要な色数の考察(List coloring, Game coloring) ・彩色に条件を課した場合の必要な色数の考察(dynamic coloring, distinguishing coloring, polychromatic coloring) 5 3 1 (Jordan の閉曲線定理) 平面内の単純閉曲線は平面をその内部と外部に分離する． 4 (1,3)-Kempe鎖は平面をその内部と外部に分離する 𝑣 の近傍の「２」からのびる(２,４)-Kempe鎖は置換可能

16 5色定理 任意の平面グラフは5-彩色をもつ 5色定理 𝑣 証明) 𝐺−𝑣 は5-彩色をもち，𝑣 の近傍に5色現れる
証明)　𝐺−𝑣 は5-彩色をもち，𝑣 の近傍に5色現れる 𝑣 の近傍の「1」を「３」に塗り替えられるか検討する ⇒「３」の近傍に「1」が現れているとき 「1」と「3」が交互に現れる (1,3)-Kempe鎖の 「1」と「3」を置換 ⇒(1,3)-Kempe鎖が 𝑣 の近傍に接続しているとき 1 𝑣 2 「四色定理」の拡張として ・「平面」を「ほかの閉曲面」に替えた場合の必要な色数の考察 ・より色数が抑えられるグラフクラス(条件)の発見(girthなど) ・彩色を拡張した概念に置き換えた場合の必要な色数の考察(List coloring, Game coloring) ・彩色に条件を課した場合の必要な色数の考察(dynamic coloring, distinguishing coloring, polychromatic coloring) 5 3 1 (Jordan の閉曲線定理) 平面内の単純閉曲線は平面をその内部と外部に分離する． 4 (1,3)-Kempe鎖は平面をその内部と外部に分離する 𝑣 の近傍の「２」からのびる(２,４)-Kempe鎖は置換可能

17 四色定理について 平面グラフを，隣接する頂点が異なるように，頂 点を塗り分けるには四色あれば十分である．
(任意の平面グラフは4-彩色をもつ) 四色定理 (Appel, Haken ‘76) 四色定理の証明では (極大)平面グラフの構造を 放電法を用いて特定する 特定したそれぞれの構造が 頂点数の小さいグラフから 4-彩色を拡張できる 「四色定理」の拡張として ・「平面」を「ほかの閉曲面」に替えた場合の必要な色数の考察 ・より色数が抑えられるグラフクラス(条件)の発見(girthなど) ・彩色を拡張した概念に置き換えた場合の必要な色数の考察(List coloring, Game coloring) ・彩色に条件を課した場合の必要な色数の考察(dynamic coloring, distinguishing coloring, polychromatic coloring)

18 3-彩色可能なグラフについて 平面上の偶三角形分割の染色数は3である 3-彩色可能な様々な平面グラフのクラスが見つかっている
ex) 三角形分割 平面上の偶三角形分割の染色数は3である 定理 (Heawood, 1898) 「四色定理」の拡張として ・「平面」を「ほかの閉曲面」に替えた場合の必要な色数の考察 ・より色数が抑えられるグラフクラス(条件)の発見(girthなど) ・彩色を拡張した概念に置き換えた場合の必要な色数の考察(List coloring, Game coloring) ・彩色に条件を課した場合の必要な色数の考察(dynamic coloring, distinguishing coloring, polychromatic coloring) 偶三角形分割： すべての頂点の次数が 偶数である三角形分割

19 偶三角形分割の生成定理 定理 (Batagalj, 1984)
平面上の偶三角形分割に4-縮約と八面体の除去を 繰り返し施すことで八面体グラフが得られる． 定理 (Batagalj, 1984) 4-縮約 a b c d x b=d 八面体の除去 a b c x y z 「四色定理」の拡張として ・「平面」を「ほかの閉曲面」に替えた場合の必要な色数の考察 ・より色数が抑えられるグラフクラス(条件)の発見(girthなど) ・彩色を拡張した概念に置き換えた場合の必要な色数の考察(List coloring, Game coloring) ・彩色に条件を課した場合の必要な色数の考察(dynamic coloring, distinguishing coloring, polychromatic coloring) ループ（と多重辺）や特異点ができる場合は変形を行わない

20 偶三角形分割の生成定理 定理 (Batagalj, 1984)
平面上の偶三角形分割に4-縮約と八面体の除去を 繰り返し施すことで八面体グラフが得られる． 定理 (Batagalj, 1984) 八面体グラフ 八面体の除去 4-縮約 「四色定理」の拡張として ・「平面」を「ほかの閉曲面」に替えた場合の必要な色数の考察 ・より色数が抑えられるグラフクラス(条件)の発見(girthなど) ・彩色を拡張した概念に置き換えた場合の必要な色数の考察(List coloring, Game coloring) ・彩色に条件を課した場合の必要な色数の考察(dynamic coloring, distinguishing coloring, polychromatic coloring) 極小グラフ：これ以上変形操作を施すことができないグラフ

21 偶三角形分割の生成定理 定理 (Batagalj, 1984)
どんな平面上の偶三角形分割も，4-縮約と八面体の除 去の逆操作を繰り返し施すことで八面体グラフから得 られる． 定理 (Batagalj, 1984) 4-縮約の逆 八面体の除去の逆 a b c d x b=d a b c x y z 「四色定理」の拡張として ・「平面」を「ほかの閉曲面」に替えた場合の必要な色数の考察 ・より色数が抑えられるグラフクラス(条件)の発見(girthなど) ・彩色を拡張した概念に置き換えた場合の必要な色数の考察(List coloring, Game coloring) ・彩色に条件を課した場合の必要な色数の考察(dynamic coloring, distinguishing coloring, polychromatic coloring)

22 変形と彩色可能性 4-縮約の逆 各変形操作は3-彩色可能性を保存する 3彩色可能 3彩色可能 3彩色可能 八面体の除去の逆 八面体の除去の逆
a b c d x b=d y z 4-縮約の逆 各変形操作は3-彩色可能性を保存する 「四色定理」の拡張として ・「平面」を「ほかの閉曲面」に替えた場合の必要な色数の考察 ・より色数が抑えられるグラフクラス(条件)の発見(girthなど) ・彩色を拡張した概念に置き換えた場合の必要な色数の考察(List coloring, Game coloring) ・彩色に条件を課した場合の必要な色数の考察(dynamic coloring, distinguishing coloring, polychromatic coloring) 八面体の除去の逆 4-縮約の逆 3彩色可能 3彩色可能 3彩色可能

23 生成定理の性質 逆操作は𝑘-彩色可能性以外にも様々な性質を保存する ・polychromatic 4-coloring 三角形分割
・Grünbaum coloring ・二部的全域四角形分割をもつ など 三角形分割 一般論を構築するよりも生成定理を 用いることで簡単に証明できることがある 「四色定理」の拡張として ・「平面」を「ほかの閉曲面」に替えた場合の必要な色数の考察 ・より色数が抑えられるグラフクラス(条件)の発見(girthなど) ・彩色を拡張した概念に置き換えた場合の必要な色数の考察(List coloring, Game coloring) ・彩色に条件を課した場合の必要な色数の考察(dynamic coloring, distinguishing coloring, polychromatic coloring) 極小グラフ

24 偶三角形分割の生成定理 平面上の偶三角形分割に4-縮約と八面体の除去を 繰り返し施すことで八面体グラフが得られる．
平面上の偶三角形分割に4-縮約と八面体の除去を 繰り返し施すことで八面体グラフが得られる． 定理 (Batagalj, 1984) 他の閉曲面への拡張 「四色定理」の拡張として ・「平面」を「ほかの閉曲面」に替えた場合の必要な色数の考察 ・より色数が抑えられるグラフクラス(条件)の発見(girthなど) ・彩色を拡張した概念に置き換えた場合の必要な色数の考察(List coloring, Game coloring) ・彩色に条件を課した場合の必要な色数の考察(dynamic coloring, distinguishing coloring, polychromatic coloring) 射影平面の展開図 トーラスの展開図 クラインボトルの展開図

25 生成定理の先行研究 極小グラフの個数 平面 1個 射影平面 27個 3個 (Kobayashi et al.2013) トーラス ？
多重辺を含まない 多重辺を含む 平面 1個 (Batagelj.1984) 射影平面 27個 (Suzuki et al.2007) 3個 (Kobayashi et al.2013) トーラス ？ 27個と6-正則 (Matsumoto et al.) クライン ボトル 「四色定理」の拡張として ・「平面」を「ほかの閉曲面」に替えた場合の必要な色数の考察 ・より色数が抑えられるグラフクラス(条件)の発見(girthなど) ・彩色を拡張した概念に置き換えた場合の必要な色数の考察(List coloring, Game coloring) ・彩色に条件を課した場合の必要な色数の考察(dynamic coloring, distinguishing coloring, polychromatic coloring)

26 クラインボトル上の生成定理 定理 (A., Matsumoto, Nakamoto and Ogano, ‘18) 6-正則グラフ
クラインボトル上のどんな偶三角形分割も4-縮約と次数2の 除去を繰り返し施すと6-正則グラフか89種類のグラフが得 られる． 定理 (A., Matsumoto, Nakamoto and Ogano, ‘18) 6-正則グラフ 4-縮約 次数2の除去 「四色定理」の拡張として ・「平面」を「ほかの閉曲面」に替えた場合の必要な色数の考察 ・より色数が抑えられるグラフクラス(条件)の発見(girthなど) ・彩色を拡張した概念に置き換えた場合の必要な色数の考察(List coloring, Game coloring) ・彩色に条件を課した場合の必要な色数の考察(dynamic coloring, distinguishing coloring, polychromatic coloring) クラインボトル上の6-正則グラフは 特徴づけられている．（Negami ‘84）

27 89種類の極小グラフ 有限グラフ 44個 無限系列 45種類 有限グラフが48個も存在してしまう理由 トーラスにおける非可縮な閉曲線は
有限グラフ　44個 無限系列　45種類 有限グラフが48個も存在してしまう理由 トーラスにおける非可縮な閉曲線は クラインボトルは、両側閉曲線と片側閉曲線とが移りあわないように、基本群が複雑になる 無限系列が存在する理由 クラインボトルは射影平面2つに分割することができ、

28 生成定理の応用 生成定理によって示されるグラフの問題は様々なものがある． 偶三角形分割の染色数とクリーク数
Grünbaum coloring bipartiteness of spanning quadrangulation polychromatic coloring N-flips and 𝑃 2 -flips in even triangulation 「四色定理」の拡張として ・「平面」を「ほかの閉曲面」に替えた場合の必要な色数の考察 ・より色数が抑えられるグラフクラス(条件)の発見(girthなど) ・彩色を拡張した概念に置き換えた場合の必要な色数の考察(List coloring, Game coloring) ・彩色に条件を課した場合の必要な色数の考察(dynamic coloring, distinguishing coloring, polychromatic coloring) polychromatic coloring を取り上げて紹介

29 美術館問題 美術館 𝑛角形のとき 𝑛 3 台いれば十分 美術館全体を監視したい 美術館の角に監視カメラを設置 できるだけ少ない台数にしたい
監視カメラは360°見張れる 本発表のタイトルにもあるpolychromatic coloringがどんなものであるかを説明するのに 関連話題である美術館問題を先にご紹介させていただいてから本発表のキーワードであるpolychromatic coloringについてご説明させていただきます。 これは美術館を上から見た図になります。 美術館の角に監視カメラを設置。 美術館問題とは、美術館に監視カメラを設置して美術館全体を見張るとき、最低何台の監視カメラを用意すれば十分か、という問題です。 まず、多角形Pに辺を加えて三角形分割を構成します。 この三角形分割の1つの面に3色現れるように塗ります。 その色の塗り方をほかの面にもどんどん拡張していくと、全ての面に3色現れるように塗ることができました。 この三角形分割はpoluchromatic proper3-coloringをもつことがわかります。 全ての色は全ての面に現れていることがわかります。 ここで、どれかの色に守衛を配備すれば美術館が監視できることがわかります。 n頂点が3色に割り振られているわけですから、1色当たり平均3分のn回使われています。どれか少なくともひとつは平均の切り捨て以下しか使われていない頂点が存在し、それが守衛集合にすればよいわけです。 すべての面に3色現れているということ、1色はすべての面をカバーしている 数学的な意味は言わない できるだけ少ない台数にしたい 美術館 𝑛角形のとき 𝑛 3 台いれば十分

30 美術館問題 美術館に監視カメラを設置して美術館全体を 見張るには最低何台設置すれば十分か？
coloringを利用したエレガントな証明 (Fisk.1978) 全ての面に3色全てが現れている 1色あたり 𝑛 3 回ほど頂点に 塗られている

31 美術館問題 美術館に監視カメラを設置して美術館全体を 見張るには最低何台設置すれば十分か？
coloringを利用したエレガントな証明 (Fisk.1978) 全ての面に3色全てが現れている 1色あたり 𝑛 3 回ほど頂点に 塗られている

32 美術館問題 美術館に監視カメラを設置して美術館全体を 見張るには最低何台設置すれば十分か？
coloringを利用したエレガントな証明 (Fisk.1978) 全ての面に3色全てが現れている polychromatic 3-coloring

33 polychromatic coloringの定義
Gのpolychromatic k-coloringとは、 k色全てがGの全ての面の境界上に現れるk-coloring polychromatc 4-coloring polychromatc 3-coloring polychromatic でない4-coloring 任意の平面グラフはpoly.1-coloringを持つ Proper coloring　では五色定理より四色定理がそうであるように、色の数が少ない方が良い定理となります。 しかしpolychromatic coloringでは全ての面にk色が現れる塗り方を持つならば、k-1色をもつことは直ちにわかるので、とあるグラフが与えられたとき、色の数を増やす方向に最良の値を探すことになります。 また、k角形面にk+1色以上の色が現れるように塗ることはできないので、 k角形面を持つ平面グラフはpolychromatic k+1-coloring を持ちません。ですから最小面サイズがkであるグラフが与えられたなら、poly.k+1-dol.をもたないことがわかる。 黄色を poly.k-colorをもつ⇒poly.(k-1)-colorをもつ 最小面サイズkのグラフはpoly.(k+1)-colorをもたない

34 任意の平面グラフはpolychromatic 2-coloringをもつ。
平面グラフのpoly.2-coloring 定理(Lovasz,1969) 任意の平面グラフはpolychromatic 2-coloringをもつ。 極大平面グラフ 任意の平面グラフ 全域四角形分割 任意の平面グラフ 極大平面グラフ 任意のグラフに辺を追加することによって極大平面グラフを作れます。 極大平面グラフはペテルセンの定理により全域四角形分割をもつ。 四角形分割は2-poly をもち、全ての辺が異なる色の頂点をもつ。 任意のグラフがpol.k-col.をもつならば、その全域グラフもpol.k-col.をもつ。 極大平面グラフは全域四角形分割をもち、 四角形分割が2-polychromatic をもつので 任意の平面グラフも2-polychromaticをもつ

35 任意の平面二部グラフはpolychromatic proper 3-coloringをもつ
平面グラフのpoly.3-coloring 三角形分割の彩色は各面に3色が現れているため， 3-彩色可能である偶三角形分割は poly. 3-coloringをもつ 任意の平面二部グラフはpolychromatic proper 3-coloringをもつ 任意の平面偶三角形分割はよく知られているとおりproper 3-cooringをもちます。 三角形面が三色で塗り分けられているのならば、三角形 極大平面グラフ 平面2部グラフ 平面2部グラフ 平面二部グラフは平面偶三角形分割から辺を取り除くとできる

36 最大次数3の平面グラフ ○ △ 定理(Horev et al.2009) 𝐾 4 𝐾 4 の細分
𝑘=2 𝑘=3 k≥4 ○ △ 定理(Horev et al.2009) 最大次数3以下の平面グラフは 𝐾 4 と 𝐾 4 を細分してできる 5頂点のグラフを除いて poly. 3-coloring を持つ k=2の時、定理1よりpoly.2-col.をもつ k=3の時、最大次数3以下のグラフはK4とK4の細分（5頂点）を除いてpoly. 3-col.可能 一般的な形のグラフにおいて予想が正しいのかは不明 𝐾 4 𝐾 4 の細分

37 3-正則平面グラフのpolychromatic
𝒌=𝟐 𝒌=𝟑 𝒌=𝟒 𝒌=𝟓 𝒌≥𝟔 ○ ≠ 𝐾 4 （Horev ’09） ？ 正十二面体 グラフ × 十二面体グラフ すべての頂点の次数が3 3-正則平面二部グラフはオイラーの公式により必ず四角形面を持つので、 3-正則平面二部グラフはpoly.5-col.を持ちません。 そして3正則二部グラフはpoly.4-col.を持つことが証明されています。 三正則平面二部グラフに関してはもう完結しているといえます。 それではこの定理をもとに色々と拡張していこうと考えたときいくつかの方針が考えられます。 まず平面以外のほかの曲面での3-正則二部グラフではどうなるかが思いつきますが、それは アニメーションを追加するようにする K=3の証明改良するかー 3-正則：最小面サイズは5以下 条件 5の時は正十二面体のみ 表の意味の説明 3-正則の具体例 K4 最小面サイズは5以下

38 3-正則平面グラフのpolychromatic
𝒌=𝟐 𝒌=𝟑 𝒌=𝟒 𝒌=𝟓 𝒌≥𝟔 ○ ≠ 𝐾 4 （Horev ’09） ？ 正十二面体 グラフ × 十二面体グラフ すべての頂点の次数が3 3-正則平面二部グラフはオイラーの公式により必ず四角形面を持つので、 3-正則平面二部グラフはpoly.5-col.を持ちません。 そして3正則二部グラフはpoly.4-col.を持つことが証明されています。 三正則平面二部グラフに関してはもう完結しているといえます。 それではこの定理をもとに色々と拡張していこうと考えたときいくつかの方針が考えられます。 まず平面以外のほかの曲面での3-正則二部グラフではどうなるかが思いつきますが、それは アニメーションを追加するようにする K=3の証明改良するかー 3-正則：最小面サイズは5以下 条件 5の時は正十二面体のみ 表の意味の説明 3-正則の具体例 K4 最小面サイズは5以下

39 3-正則平面グラフのpolychromatic
𝒌=𝟐 𝒌=𝟑 𝒌=𝟒 𝒌=𝟓 𝒌≥𝟔 ○ ≠ 𝐾 4 （Horev ’09） ？ 正十二面体 グラフ × 予想 三角形面を持たない任意の2-連結3-正則平面グラフは odd prism を除き、polychromatic 4-coloringをもつ。 3-正則平面二部グラフはオイラーの公式により必ず四角形面を持つので、 3-正則平面二部グラフはpoly.5-col.を持ちません。 そして3正則二部グラフはpoly.4-col.を持つことが証明されています。 三正則平面二部グラフに関してはもう完結しているといえます。 それではこの定理をもとに色々と拡張していこうと考えたときいくつかの方針が考えられます。 まず平面以外のほかの曲面での3-正則二部グラフではどうなるかが思いつきますが、それは アニメーションを追加するようにする 3-正則：最小面サイズは5以下 条件 5の時は正十二面体のみ 表の意味の説明 3-正則の具体例 K4

40 3-正則平面グラフのpolychromatic
予想 三角形面を持たない任意の2-連結3-正則平面グラフは odd prism を除き、polychromatic 4-coloringをもつ。 7-prism 連結度１ 3-正則平面二部グラフはオイラーの公式により必ず四角形面を持つので、 3-正則平面二部グラフはpoly.5-col.を持ちません。 そして3正則二部グラフはpoly.4-col.を持つことが証明されています。 三正則平面二部グラフに関してはもう完結しているといえます。 それではこの定理をもとに色々と拡張していこうと考えたときいくつかの方針が考えられます。 まず平面以外のほかの曲面での3-正則二部グラフではどうなるかが思いつきますが、それは 2連結 Odd　prism ：色 ”1” ”2” ：色 ”3” ”4”

41 3-正則平面二部グラフのpoly. coloring
定理 (Horev et al.2011) どんな3-正則平面2部グラフも polychromatic proper 4-coloringを持つ。 3-正則平面2部グラフ 平面偶三角形分割の双対グラフは3-正則平面2部グラフである

42 偶三角形分割の生成定理（再 掲） 定理 (Batagalj, 1984)
どんな平面上の偶三角形分割も，4-縮約と八面体の除 去の逆操作を繰り返し施すことで八面体グラフから得 られる． 定理 (Batagalj, 1984) 4-縮約の逆 八面体の除去の逆 a b c d x b=d a b c x y z 「四色定理」の拡張として ・「平面」を「ほかの閉曲面」に替えた場合の必要な色数の考察 ・より色数が抑えられるグラフクラス(条件)の発見(girthなど) ・彩色を拡張した概念に置き換えた場合の必要な色数の考察(List coloring, Game coloring) ・彩色に条件を課した場合の必要な色数の考察(dynamic coloring, distinguishing coloring, polychromatic coloring) この生成定理を双対グラフで考える

43 3連結3-正則2部グラフの生成定理 補題 正八面体グラフ Cube
任意の3連結3-正則2部グラフ はCubeから 2-bridging と hexagon additionの2つの変形操作を 繰り返すことで得られる。 正八面体グラフ Cube 3正則グラフの双対グラフである三角形分割の生成定理を利用しているので3連結という条件がついていますが、定理1では連結度関係なく証明されています。

44 3連結3-正則2部グラフの生成定理 補題 2-bridging hexagon addition
任意の3連結3-正則2部グラフ はCubeから 2-bridging と hexagon additionの2つの変形操作を 繰り返すことで得られる。 2-bridging hexagon addition 2つの変形操作は3正則２部性を保存します

45 射影平面でも生成定理を利用して同様の定理が証明されている
3連結3-正則2部グラフの生成定理 2つの変形操作2-bridgingとhexagon additionは polychromatic 4-coloring性を保存する。 2-bridging hexagon addition Cube 各頂点の色の塗られ方によって場合分けがいくつかそんざいし、それぞれについてうまく塗れる例が存在します。 cubeがこのようにpoly.4-col.を持つことがわかるり、全ての3連結3正則二部グラフはpoly.4-col.をもつことがわかりました 連結度が2以下のものは、別途証明が必要になります。 私は奇角形面を2つもつ3正則グラフにおいてもこれと同様の生成定理を証明しました。 射影平面でも生成定理を利用して同様の定理が証明されている

46 3-正則平面グラフのpolychromatic
𝒌=𝟐 𝒌=𝟑 𝒌=𝟒 𝒌=𝟓 𝒌≥𝟔 ○ ≠ 𝐾 4 （Horev ’09） 二部グラフ 〇 正十二面体 グラフ × 非二部グラフ ？ 予想 三角形面を持たない任意の2-連結3-正則平面グラフは odd prism を除き、polychromatic 4-coloringをもつ 3-正則平面二部グラフはオイラーの公式により必ず四角形面を持つので、 3-正則平面二部グラフはpoly.5-col.を持ちません。 そして3正則二部グラフはpoly.4-col.を持つことが証明されています。 三正則平面二部グラフに関してはもう完結しているといえます。 それではこの定理をもとに色々と拡張していこうと考えたときいくつかの方針が考えられます。 まず平面以外のほかの曲面での3-正則二部グラフではどうなるかが思いつきますが、それは アニメーションを追加するようにする 3-正則：最小面サイズは5以下 条件 5の時は正十二面体のみ 表の意味の説明 3-正則の具体例 K4

47 dynamic coloring ・proper coloringは1-dynamic この3-coloringは2-dynamicか？
・次数が 𝑟 以上の頂点の近傍に 𝑟 色以上現れる ・次数が 𝑟 未満の頂点の近傍がすべて異なる色をもつ ・proper coloringは1-dynamic 口語表現に近い定義 r-dynamic　coloring 次数がr以上の頂点には，r色以上現れ， 次数がr未満の頂点は近傍がすべて異なる色で塗られているようなproper　coloring 一般的でやや抽象的な例 この3-coloringは2-dynamicか？ →No

48 定義 𝑟=3の場合を考える このグラフは 3-dynamic 4-coloringをもつか？ (1+3) 色必要 →No
𝐺=(𝑉,𝐸) の proper 𝑘-coloring 𝑐とは、 写像 𝑐 :𝑉→{1,⋯,𝑘} で どの隣接する2頂点 𝑢,𝑣 に対しても𝑐 𝑢 ≠𝑐(𝑣) が成り立つものである 𝐺=(𝑉,𝐸) の 𝑟-dynamic coloring は、以下の条件を満たすproper coloring ・次数が 𝑟 以上の頂点の近傍に 𝑟 色以上現れる ・次数が 𝑟 未満の頂点の近傍がすべて異なる色をもつ 𝑟=3の場合を考える 口語表現に近い定義 r-dynamic　coloring 次数がr以上の頂点には，r色以上現れ， 次数がr未満の頂点は近傍がすべて異なる色で塗られているようなproper　coloring 一般的でやや抽象的な例 このグラフは 3-dynamic 4-coloringをもつか？ (1+3) 色必要 →No

49 定義 𝑟=3の場合を考える このグラフは 3-dynamic 4-coloringをもつか？ →No
𝐺=(𝑉,𝐸) の proper 𝑘-coloring 𝑐とは、 写像 𝑐 :𝑉→{1,⋯,𝑘} で どの隣接する2頂点 𝑢,𝑣 に対しても𝑐 𝑢 ≠𝑐(𝑣) が成り立つものである 𝐺=(𝑉,𝐸) の 𝑟-dynamic coloring は、以下の条件を満たすproper coloring ・次数が 𝑟 以上の頂点の近傍に 𝑟 色以上現れる ・次数が 𝑟 未満の頂点の近傍がすべて異なる色をもつ 𝑟=3の場合を考える 口語表現に近い定義 r-dynamic　coloring 次数がr以上の頂点には，r色以上現れ， 次数がr未満の頂点は近傍がすべて異なる色で塗られているようなproper　coloring 一般的でやや抽象的な例 このグラフは 3-dynamic 4-coloringをもつか？ →No

50 定義 𝐺=(𝑉,𝐸) の proper 𝑘-coloring 𝑐とは、 写像 𝑐 :𝑉→{1,⋯,𝑘} で どの隣接する2頂点 𝑢,𝑣 に対しても𝑐 𝑢 ≠𝑐(𝑣) が成り立つものである 𝐺=(𝑉,𝐸) の 𝑟-dynamic coloring は、以下の条件を満たすproper coloring ・次数が 𝑟 以上の頂点の近傍に 𝑟 色以上現れる ・次数が 𝑟 未満の頂点の近傍がすべて異なる色をもつ 口語表現に近い定義 r-dynamic　coloring 次数がr以上の頂点には，r色以上現れ， 次数がr未満の頂点は近傍がすべて異なる色で塗られているようなproper　coloring 一般的でやや抽象的な例 3-dynamic 5-coloring

51 定義 全頂点の色が異なるならば、 そのcoloring は 𝑟-dynamic である 𝑟 の値に対する𝑘 の最小値を知りたい
𝐺=(𝑉,𝐸) の proper 𝑘-coloring 𝑐とは、 写像 𝑐 :𝑉→{1,⋯,𝑘} で どの隣接する2頂点 𝑢,𝑣 に対しても𝑐 𝑢 ≠𝑐(𝑣) が成り立つものである 𝐺=(𝑉,𝐸) の 𝑟-dynamic coloring は、以下の条件を満たすproper coloring ・次数が 𝑟 以上の頂点の近傍に 𝑟 色以上現れる ・次数が 𝑟 未満の頂点の近傍がすべて異なる色をもつ 全頂点の色が異なるならば、 そのcoloring は 𝑟-dynamic である 口語表現に近い定義 r-dynamic　coloring 次数がr以上の頂点には，r色以上現れ， 次数がr未満の頂点は近傍がすべて異なる色で塗られているようなproper　coloring 一般的でやや抽象的な例 𝑟 の値に対する𝑘 の最小値を知りたい 𝑟-dynamic chromatic number : 𝜒 𝑟 𝑑 𝐺

52 定義 𝜒 1 𝑑 𝐺 =3 𝜒 2 𝑑 𝐺 =3 𝜒 3 𝑑 𝐺 =5 口語表現に近い定義 r-dynamic　coloring 次数がr以上の頂点には，r色以上現れ， 次数がr未満の頂点は近傍がすべて異なる色で塗られているようなproper　coloring 一般的でやや抽象的な例 一般に 𝜒 1 𝑑 𝐺 ≤ 𝜒 2 𝑑 𝐺 ≤⋯≤ 𝜒 𝑟−1 𝑑 𝐺 ≤ 𝜒 𝑟 𝑑 𝐺 ≤⋯ 𝜒 1 𝑑 𝐺 と 𝜒 2 𝑑 𝐺 の差が定数で抑えられないことが知られている

53 平面グラフの 2-dynamic coloring
平面グラフにおいては 𝜒 2 𝑑 𝐺 と 𝜒(𝐺) はほとんど差がない ＊四色定理から 𝜒 𝐺 ≤4 定理 (Kim, Lee and Park, 2013 ) 𝐺 : 𝐶 5 を除く平面グラフ　⇒　 𝜒 2 𝑑 𝐺 ≤4 𝐶 5 Kim Lee and park proved that 2-dynamic chromatic number for planar graph is at most 5. This value is sharp. They also proved that C_5 is the only graph whose 2-dynamic chromatic number is exactly equal to 5. Let’s check that C_5 needs 5colors for 2-dynamic coloring. Since the maximum degree of C_5 is 2, it suffices that we consider only the proper coloring for its square. Therefore \chi d 2 C_5 is equal to the chromatic number of K_5. Thus, \chi d 2 C_5 =5. 𝜒 2 𝑑 𝐶 5 =5

54 平面グラフの 3-dynamic coloring
平面グラフでも 𝑟=3 では 𝜒 3 𝑑 𝐺 と 𝜒(𝐺) に差が生じる 定理 (Loeb, Mahoney, Reinger and Wise, 2017) 𝐺 : 平面グラフ　 ⇒　 𝜒 3 𝑑 𝐺 ≤10 𝐺 𝐺′ 4頂点で3色が必要 3頂点で3色が必要 The theorem is a result about 3-dynamic coloring. For planar graph G, \chi d3G is at most 10. However, actually they proved this theorem for toroidal graph, so this result may not be sharp. In current study, a graph which needs most colors for 3-dynamic is this graph. As far as it is currently known, this graph requiring 7 colors to paint 3-dynamically is an example that requires the greatest number of colors. Since the maximum degree of this graph is 3, it suffices that we consider only the proper coloring for its square. And its maximum degree is 3 and its diameter is 2, square of this graph is K_7. Thus we need 7 colors to paint this graph 3dynamically. I don’t know there exists a graph which needs 10 colors, or we could obtain better evaluation. 辺の追加 𝜒 3 𝑑 𝐺 =7 𝜒 3 𝑑 𝐺′ =6

55 平面三角形分割のdynamic coloring
定理（A., Kawasaki, S.-J., Nakamoto, Ozeki, ‘18） sharp 𝐺 : 平面三角形分割　⇒　 𝜒 3 𝑑 𝐺 ≤5 𝐺 That’s why we study about 3-dynamic coloring for planar triangulation. Since triangulations are the graph class s.t. the number of edges is maximum among embedded graphs. If G is a planar triangulation, then \chi 3dg is at most 5 平面三角形分割とは，各面が三角形になるように平面に埋め込まれたグラフ． 𝜒 3 𝑑 𝐺 =5

56 証明 放電法を用いて次を示す 補題 平面三角形分割は次のいずれかの構造をもつ 次数3の頂点 隣接する2つの次数4の頂点
隣接する次数4と6の頂点 隣接する次数4と7の頂点 次数5の頂点 補題 We’ll introduce outline of our main theorem briefly. First, by using discharging method, we specify the unavoidable set. that is, ~. Then we introduce 6 transformations which 3-dynamic 5-colorability. Note that although for ordinarily proper coloring, we have to prepare more than 600 configurations, we have to prepare 5 ones. There is a big difference between them.

57 証明 補題の証明） グラフにいずれの構造も現れないと仮定する． 以下のルールで放電を行う 全ての次数 𝑖 の頂点に，6−𝑖 の電荷を与える．
三角形分割では 𝑣∈𝑉 (6− deg 𝐺 𝑣 ) =12が成り立つため 電荷の総和は12． 各次数4の頂点からその近傍に だけ電荷を移動させる． We’ll introduce outline of our main theorem briefly. First, by using discharging method, we specify the unavoidable set. that is, ~. Then we introduce 6 transformations which 3-dynamic 5-colorability. Note that although for ordinarily proper coloring, we have to prepare more than 600 configurations, we have to prepare 5 ones. There is a big difference between them.

58 証明 補題の証明） 放電のルール 次数 𝑖 に，6−𝑖 の電荷 電荷の総和は12． 次数4の頂点からその近傍に 1 2 電荷を移動．
放電のルール 次数 𝑖 に，6−𝑖 の電荷 電荷の総和は12． 次数4の頂点からその近傍に 電荷を移動． 次数4の頂点： 次数4の頂点どうしは隣接しないため，電荷は0． 次数 𝑖≥8 以上の頂点: 隣接する次数4の頂点はたかだか 1 2 𝑖 個 電荷は 6−𝑖 × 1 2 𝑖 ≤0. 次数6と7の頂点: 次数4の頂点に隣接しないので，電荷は0以下. 次数4の頂点どうしは隣接しないため，次数4の頂点の電荷は0． また，次数 𝑖≥8 以上の頂点に隣接する次数4の頂点はたかだか 1 2 𝑖 個で電荷も 6−𝑖 × 1 2 𝑖 ≤0. 次数6と7の頂点は次数4の頂点に隣接しないので，電荷の値は0以下 よって，すべての頂点の電荷の総和が府になってしまったので矛盾 放電後，電荷の総和が0以下になり矛盾□

59 証明 特定した5つの不可避集合それぞれに対して， 3-dynamic 5-colorable 性を保存する変形を用意する
次数3の頂点 次数5の頂点 隣接する次数4と7の頂点 隣接する次数4と6の頂点 隣接する次数4の頂点 We’ll introduce outline of our main theorem briefly. First, by using discharging method, we specify the unavoidable set. that is, ~. Then we introduce 6 transformations which 3-dynamic 5-colorability. Note that although for ordinarily proper coloring, we have to prepare more than 600 configurations, we have to prepare 5 ones. There is a big difference between them. 多重辺が発生する場合には変形を行わない

60 もし 𝐺’ が 3-dynamic 5-coloring をもつならば 𝐺 もまた自動的に 3-dynamic 5-coloring をもつ
証明 特定した5つの不可避集合それぞれに対して， 3-dynamic 5-colorable 性を保存する変形を用意する ex)次数5の頂点の近傍 𝐺 𝐺′ Each transformation preserve 3-dynamic 5-colorability. For example, assume that G’ is obtained from G by a contraction around a vertex of degree 5. If G’ has a 3d 5-coloring, then we can extend the coloring to that of G. もし 𝐺’ が 3-dynamic 5-coloring をもつならば 𝐺 もまた自動的に 3-dynamic 5-coloring をもつ

61 証明 6つの変形操作が行えないグラフを特定し， それぞれが 3-dynamic 5-coloringをもつことを示す．
We’ll introduce outline of our main theorem briefly. First, by using discharging method, we specify the unavoidable set. that is, ~. Then we introduce 6 transformations which 3-dynamic 5-colorability. Note that although for ordinarily proper coloring, we have to prepare more than 600 configurations, we have to prepare 5 ones. There is a big difference between them.

62 𝐺 : トーラス，クラインボトル上の三角形分割 ⇒ 𝜒 3 𝑑 𝐺 ≤7
他の閉曲面への拡張 定理 sharp 𝐺 : 射影平面上の三角形分割　⇒　 𝜒 3 𝑑 𝐺 ≤6 𝜒 𝐾 6 = 𝜒 3 𝑑 𝐾 6 =6 𝐾 6 定理 トーラスではsharp 𝐺 : トーラス，クラインボトル上の三角形分割　⇒　 𝜒 3 𝑑 𝐺 ≤7 𝜒 𝐾 7 = 𝜒 3 𝑑 𝐾 7 =7 𝐾 7

63 他の閉曲面への拡張 定理 𝐺 : トーラス上の三角形分割 ⇒ 𝜒 3 𝑑 𝐺 ≤7 証明）トーラスの次数6以下の頂点に以下の変形を導入する．
𝐺 : トーラス上の三角形分割　⇒　 𝜒 3 𝑑 𝐺 ≤7 証明）トーラスの次数6以下の頂点に以下の変形を導入する． これらの逆変形は3-dynamic 7-coloring 性を保存する

64 他の閉曲面への拡張 定理 𝐺 : トーラス上の三角形分割 ⇒ 𝜒 3 𝑑 𝐺 ≤7 次数4の変形ができないときを考える．
𝐺 : トーラス上の三角形分割　⇒　 𝜒 3 𝑑 𝐺 ≤7 次数4の変形ができないときを考える． 𝑣 𝑣 0 の縮約で 𝑣 0 𝑣 2 が多重辺になるとする． このとき非可縮な長さ3の閉路 𝑣 0 𝑣 𝑣 2 が存在する 𝑣 0 𝑣 𝑣 1 𝑣 2 𝑣 3 𝐺 から 𝑣 を取り除いたうえで， 閉路 𝑣 0 𝑣 3 𝑣 2 と 𝑣 0 𝑣 1 𝑣 2 に沿って閉曲面を切り開き， それぞれの境界に円盤を張り合わせて蓋をすれば 球面上の三角形分割 𝐺′ が得られる 平面での結果より 𝐺′ は3-dynamic 5-coloring をもつ. ここで 𝑣 0 , 𝑣 0 ′ を色「６」に， 𝑣 2 , 𝑣 2 ′ を色「７」に塗り替え， 𝑣 に近傍に現れていない色が少なくとも3色あり， 𝐺 の 3-dynamic 7-coloring が得られる

65 他の閉曲面への拡張 定理 𝐺 : トーラス上の三角形分割 ⇒ 𝜒 3 𝑑 𝐺 ≤7 次数4の変形ができないときを考える．
𝐺 : トーラス上の三角形分割　⇒　 𝜒 3 𝑑 𝐺 ≤7 次数4の変形ができないときを考える． 𝑣 𝑣 0 の縮約で 𝑣 0 𝑣 2 が多重辺になるとする． このとき非可縮な長さ3の閉路 𝑣 0 𝑣 𝑣 2 が存在する 𝑣 0 ′ 𝑣 0 𝐺 から 𝑣 を取り除いたうえで， 閉路 𝑣 0 𝑣 3 𝑣 2 と 𝑣 0 𝑣 1 𝑣 2 に沿って閉曲面を切り開き， それぞれの境界に円盤を張り合わせて蓋をすれば 球面上の三角形分割 𝐺′ が得られる ここで 𝑣 と 𝑣′ を除去し，アニュラスの切り口である 𝑣 0 𝑣 1 𝑣 2 と 𝑣 0 𝑣 3 𝑣 2 に円盤を張り合わせることで 球面上の三角形分割が得られる 𝑣 3 𝑣 1 𝑣′ 𝑣 𝑣 2 ′ 𝑣 2 平面での結果より 𝐺′ は3-dynamic 5-coloring をもつ. ここで 𝑣 0 , 𝑣 0 ′ を色「６」に， 𝑣 2 , 𝑣 2 ′ を色「７」に塗り替え， 𝑣 に近傍に現れていない色が少なくとも3色あり， 𝐺 の 3-dynamic 7-coloring が得られる

66 他の閉曲面への拡張 定理 𝐺 : トーラス上の三角形分割 ⇒ 𝜒 3 𝑑 𝐺 ≤7 次数4の変形ができないときを考える．
𝐺 : トーラス上の三角形分割　⇒　 𝜒 3 𝑑 𝐺 ≤7 次数4の変形ができないときを考える． 𝑣 𝑣 0 の縮約で 𝑣 0 𝑣 2 が多重辺になるとする． このとき非可縮な長さ3の閉路 𝑣 0 𝑣 𝑣 2 が存在する 𝑣 0 ′ 𝑣 0 𝐺 から 𝑣 を取り除いたうえで， 閉路 𝑣 0 𝑣 3 𝑣 2 と 𝑣 0 𝑣 1 𝑣 2 に沿って閉曲面を切り開き， それぞれの境界に円盤を張り合わせて蓋をすれば 球面上の三角形分割 𝐺′ が得られる ここで 𝑣 と 𝑣′ を除去し，アニュラスの切り口である 𝑣 0 𝑣 1 𝑣 2 と 𝑣 0 𝑣 3 𝑣 2 に円盤を張り合わせることで 球面上の三角形分割が得られる 𝑣 3 𝑣 1 𝑣 2 ′ 𝑣 2 平面での結果より 𝐺′ は3-dynamic 5-coloring をもつ. ここで 𝑣 0 , 𝑣 0 ′ を色「６」に， 𝑣 2 , 𝑣 2 ′ を色「７」に塗り替え， 𝑣 に近傍に現れていない色が少なくとも3色あり， 𝐺 の 3-dynamic 7-coloring が得られる

67 他の閉曲面への拡張 定理 𝐺 : トーラス上の三角形分割 ⇒ 𝜒 3 𝑑 𝐺 ≤7 次数4の変形ができないときを考える．
𝐺 : トーラス上の三角形分割　⇒　 𝜒 3 𝑑 𝐺 ≤7 次数4の変形ができないときを考える． 𝑣 𝑣 0 の縮約で 𝑣 0 𝑣 2 が多重辺になるとする． このとき非可縮な長さ3の閉路 𝑣 0 𝑣 𝑣 2 が存在する 「6」 「２」 𝐺 から 𝑣 を取り除いたうえで， 閉路 𝑣 0 𝑣 3 𝑣 2 と 𝑣 0 𝑣 1 𝑣 2 に沿って閉曲面を切り開き， それぞれの境界に円盤を張り合わせて蓋をすれば 球面上の三角形分割 𝐺′ が得られる 「1」 ここで 𝑣 と 𝑣′ を除去し，アニュラスの切り口である 𝑣 0 𝑣 1 𝑣 2 と 𝑣 0 𝑣 3 𝑣 2 に円盤を張り合わせることで 球面上の三角形分割が得られる 「７」 平面での結果より 𝐺′ は3-dynamic 5-coloring をもつ. ここで 𝑣 0 , 𝑣 0 ′ を色「６」に， 𝑣 2 , 𝑣 2 ′ を色「７」に塗り替え 𝑣 に近傍に現れていない色が少なくとも3色あり， 𝐺 の 3-dynamic 7-coloring が得られる

68 dynamic coloringまとめ sharp 定理 (Loeb, Mahoney, Reinger and Wise 2017)
𝐺 : 平面グラフ　 ⇒　 𝜒 3 𝑑 𝐺 ≤10 定理 sharp 𝐺 : 平面三角形分割　⇒　 𝜒 3 𝑑 𝐺 ≤5 残されている問題 ・一般の平面グラフの 𝜒 3 𝑑 𝐺 の評価の改良 ・射影平面の三角形分割で 𝜒 3 𝑑 𝐺 =6 であるものの特徴づけ ・クラインボトル上の三角形分割における 𝜒 3 𝑑 𝐺 の評価

69 ご清聴ありがとうございました