位相幾何的グラフ理論・未解決問題

1. 有限平面被覆を持つグラフは射影平面に埋め込み可能か？ （予想：YES）

   これは「1-2-∞予想」と呼ばれています． 現段階では，K_1,2,2,2が有限平面被覆を持たなければ， この問題が肯定的に解決したことになります．

2. 種数２以上の閉曲面の既約三角形分割の中で， 頂点数最大のものは，長さ３の分離閉路を含むか？ （予想：YES）

   どの辺を縮約しても，グラフの単純性が崩れてしまう三角形分割を 既約な三角形分割と呼びます． 一般に，閉曲面を固定すると，その既約三角形分割は有限個しか存在しません． この予想が正しいと，既約三角形分割の頂点数に かなりよい上界が与えられます．

3. それぞれ射影平面上に埋め込まれた２つにグラフを 辺のみで交わるように重ねたとき， その交差点の個数は ２つのグラフの辺表現度の積に等しいか？ （予想：YES） 【済み】

   射影平面上のグラフの辺表現度とは， それと非可縮単純閉曲線との交差点の最小値のことです． その積が交差点の個数の上界になることは簡単にわかります．

   ★この予想はすでに，次の論文の中で，肯定的に解決されています． 実に簡潔な証明です．
   

   D. Archdeacon and C.P. Bonnington, Two maps on one surface, preprint, 1997.

4. 閉曲面上のグラフとその双対グラフを辺だけで交差するように 重ねたときの交差点の最小数がそのグラフの辺数を越えないことは 明らかです． その等号が成立するグラフを特徴づけてください．

   同様に，自分と自分を重ねたときの交差数を考えるのも， おもしろいかもしれません．

5. 十分に大きな n を考えると， n次元立方体グラフのどんな空間埋め込みも， 自明でない結び目または絡み目を含むか？ ただし，空間埋め込みは，各辺がまっすぐな線分になっているものだけを考えます． （予想：YES）

   すでに，完全グラフや完全２部グラフに対して， 肯定的な答えが得られています．

6. 完全グラフ K_n を埋め込んで作られる 閉曲面の三角形分割の looseness の最大値を決定してください． （予想：　n によらない上界があると思います．）

   閉曲面上の三角形分割の頂点に任意にn+3色を着色すると， かならずどこかの三角形の面の３つの頂点が異なる３色になってしまうとき， その三角形分割は n-loosely tightであるといい， n-loosely tight となる最小の n の値を その三角形分割の looseness と呼びます． looseness が 0 の三角形分割は自動的に完全グラフになります．

7. 与えられた閉曲面上の三角形分割の looseness の最小値を決定してください．

   地図色分け定理などで知られている完全グラフの埋め込みから得られる 三角形分割の looseness は 0 になっています． したがって，問題の最小値は閉曲面の種数に関して単調増加になるのではなく， 適当な周期で 0 に戻ってしまいます．

8. 閉曲面上のグラフで，次数列が等しいものどうしを互いに変換しできる 変形操作を見つけてください．

   日本の位相幾何学的グラフ理論では， 俗に「変形ネタ」と呼ばれる研究が盛んです． この問題はその究極的な形です．

9. 適当な計量が定義された閉曲面上のグラフを考えます． 辺の長さの総和が最小になるように， グラフを isotopy の範囲で変形したときに， その極限が存在するグラフを特徴づけてください．

   例えば，１つの頂点の近傍がクモの巣のようになっていると， 辺の総和をほとんど変えずに，その部分を縮小していくことができます． この場合，クモの巣の部分はその頂点に吸収されてしまい， その操作の極限はものとのグラフとは異なってしまいます． そのような現象が起こらないグラフはどんなものかを知りたいわけです．

10. 閉曲面上の三角形分割において， 対角変形をどんなに繰り返しても 縮約可能な辺を作ることができないとき， その三角形分割を擬最小三角形分割といいます． 擬最小三角形分割で，最小の三角形分割ではないものはあるでしょうか？ （予想：NO． しかし，答えは"YES"です．） 【済み】

    三角形分割の対角変形に理論において， 擬最小三角形分割は非常に重要な概念ですが， その具体的な姿はあまりよくわかっていません．

    ★ 最近，次の論文に書かれている定理を用いることで， K_4(m)とK_6(m)がそれぞれ 向き付け可能と不可能な閉曲面の擬最小三角形分割になることが わかりました． したがって，上の問いの答えは"YES"ということになります．
    

    D. Archdeacon, The medial graph and voltage-current duality, Discrete Math. 104 (1992) 111-141.

11. 種数３の向き付け不可能な閉曲面上の6-連結な三角形分割で， その埋め込みが一意でないものは存在するか？ （予想：YES）

    5-連結な三角形分割ならば， そのようなものは無限個存在します． また，三角形分割でない6-連結グラフならば， やはりそのようなものは無限個存在します．

12. 極大平面グラフを有限被覆に持つ非平面的グラフは， 射影平面の三角形分割になるか？ （予想：YES）

    簡単な計算によって，その被覆が２重か６重であることがわかります． 6重のときには，もはや射影平面的にはなりません． 「1-2-∞予想」が正しければ，この場合は自動的に排除されますが， このくらいの事実なら，初等的に証明したいですね．

13. ２つ3-連結グラフ G と G^* の組が 互いに双対グラフになるように， 閉曲面に埋め込まれるならば， その埋め込みは一意的でしょうか？ （予想：YES）

    これは，やや安易な問題です． おそらく，2-連結では埋め込みが一意的でないものが作れるでしょう． まず，それを構成してみましょう． それに成功したら，「3-連結」の部分を適当な条件に変えて， 定理を作ってください． その条件がどこまで落とせるかが，勝負です．