Loading article…
グラフ理論の数学分野において、スナークとは、頂点ごとにちょうど3つの辺を持ち、かつその辺を3色だけで着色できない無向グラフのことである。自明なケースを避けるため、スナークには連結性やサイクルの長さに関する追加の条件が課されることが多い。スナークは無限に存在する。
四色定理の等価形式の一つは、すべてのスナークは非平面グラフであるというものである。スナークの研究は、1880年のピーター・G・テイトの四色定理に関する研究に端を発するが、その名称ははるかに新しく、 1976年にマーティン・ガードナーによって付けられた。彩色以外にも、スナークはグラフ理論における他の難問とも関連している。電子ジャーナル・オブ・コンビナトリクス誌に寄稿したミロスラフ・クラドニーとマーティン・シュコヴィエラは、
グラフ理論におけるさまざまな重要かつ困難な問題（サイクル二重被覆予想や5フロー予想など）の研究において、スナークと呼ばれる興味深いがやや謎めいたグラフに出会うことがある。その定義は単純であるにもかかわらず、そして1世紀以上にわたる研究にもかかわらず、その性質と構造はほとんど解明されていない。[ 1 ]
彼らが指摘する問題に加えて、WT Tutteのスナーク予想は、スナークのグラフマイナーとしてのPetersen グラフの存在に関するものです。その証明は長い間発表されていますが未発表のままであり、どこにもゼロがない 4-フローの存在の特殊なケースを解決するものです。
スナークは、ルイス・キャロルの詩「スナーク狩り」に登場する謎めいた捉えどころのない物体にちなんで、1976年にアメリカの数学者マーティン・ガードナーによって名付けられました。[ 2 ]しかし、この種のグラフの研究は、その名前よりもかなり古いものです。ピーター・G・テイトは、1880年に4色定理が「スナークは平面ではない」という命題と同等であることを証明し、スナークの研究を開始しました。[ 3 ] スナークとして知られている最初のグラフはピーターセングラフです。これは、 1898年にジュリアス・ピーターセンによってスナークであることが証明されましたが、 [ 4 ] 1886年にはアルフレッド・ケンプによって別の目的で既に研究されていました。[ 5 ]
次に知られている4匹のスナークは
1975年、ルーファス・アイザックスはブラヌシャの方法を一般化して、2つの無限スナーク族、すなわちフラワースナークとブラヌシャ-デカルト-セケレススナークを構築した。ブラヌシャ-デカルト-セケレススナーク族には、2つのブラヌシャスナーク、デカルトスナーク、セケレススナークが含まれる。アイザックスはまた、ブラヌシャ-デカルト-セケレス族にも属さず、フラワースナークでもない30頂点スナーク、ダブルスタースナークを発見した。[ 9 ] 1976年にアイザックスによって発表された別の無限族、ルーペキンスナークは、F. ルーペキンに帰属する。これには、ピーターセングラフから派生した2つの22頂点スナークが含まれる。[ 10 ] 50頂点ワトキンススナークは1989年に発見された。[ 11 ]
もう一つ注目すべき3辺彩色不可能な立方体グラフは、12個の頂点を持つティーツェのグラフです。ハインリヒ・フランツ・フリードリヒ・ティーツェが1910年に発見したように、これは6色を必要とするメビウスの帯の分割の境界を形成します。 [ 12 ]しかし、三角形が含まれているため、一般にはスナークとはみなされません。スナークの厳密な定義の下では、最小のスナークはペーターセングラフとブラヌシャスナークであり、それに続いて6つの異なる20頂点スナークがあります。[ 13 ]
2012年にGunnar Brinkmann、Jan Goedgebeur、Jonas Hägglund、Klas Markströmによって、頂点数が36個まで（厳密な定義による）、および34個まで（より緩やかな定義による）のすべてのスナークのリストが作成されました。[ 13 ]与えられた偶数個の頂点に対するスナークの数は、頂点数に対して少なくとも指数関数的に増加します。[ 14 ]（奇数次数の頂点を持つため、ハンドシェイク補題により、すべてのスナークは偶数個の頂点を持たなければなりません。）[ 15 ] OEISシーケンスA130315には、非自明なスナークの数が含まれています。小さな値の頂点[ 16 ]
スナークの正確な定義は著者によって異なるが、[ 13 ] [ 9 ]一般的には、各頂点にちょうど3つの辺を持つ立方グラフで、辺を3色だけで着色できないものを指す。ヴィジングの定理によれば、立方グラフの辺に必要な色の数は3色（「クラス1」グラフ）または4色（「クラス2」グラフ）であるため、スナークはクラス2の立方グラフである。しかし、スナークが自明な理由でクラス2になる場合や、より小さなグラフから自明な方法で構築される場合を避けるために、接続性やサイクル長に関する追加の制約が課されることが多い。具体的には、次の通りである。
これらの定義では、周囲長が最大5までの制約しか考慮されていませんが、周囲長が任意に大きいスナークも存在します。[ 17 ]
ピーター・G・テイトの研究により、すべてのスナークが非平面である場合に限り、4色定理が真であることが確立されました。 [ 3 ]この定理は、すべての平面グラフの頂点が4色で彩色されることを示していますが、テイトは、最大平面グラフの4頂点彩色を、立方体で平面である双対グラフの3辺彩色に変換する方法、およびその逆の方法を示しました。したがって、平面スナークは、必然的に4色定理の反例の双対になります。したがって、4色定理のその後の証明[ 18 ]は、すべてのスナークが非平面であることも示しています。[ 19 ]
すべてのスナークは非ハミルトンです。3次グラフにハミルトン閉路がある場合、閉路に2色を交互に使用し、残りの辺に3番目の色を使用することで、常に辺を3色で彩色できます。しかし、多くの既知のスナークは、準ハミルトングラフという意味でハミルトンに近いものです。任意の1つの頂点を削除すると、ハミルトン部分グラフが残ります。準ハミルトンスナークは双臨界でなければなりません。任意の2つの頂点を削除すると、3辺彩色可能な部分グラフが残ります。[ 20 ] 3次グラフの奇数性は、各頂点を1回カバーする任意のサイクルシステム（ 2因子）における奇数サイクルの最小数として定義されます。ハミルトン閉路を持たないのと同じ理由で、スナークは正の奇数性を持ちます。完全に偶数の2因子は3辺彩色につながり、その逆もまた然りです。頂点の数に比例して奇数が増加するスナークの無限族を構築することが可能である。[ 15 ]
サイクル二重被覆予想は、橋のないグラフでは、各辺を2回覆うサイクルの集合が見つかるか、あるいは同等に、グラフを曲面に埋め込むと、埋め込みのすべての面が単純サイクルになる、と仮定している。3次グラフが3辺彩色されている場合、各色のペアによって形成されるサイクルからなるサイクル二重被覆が存在する。したがって、3次グラフの中で、スナークは唯一の反例である。より一般的には、スナークはこの予想の難しいケースである。スナークで真であれば、すべてのグラフで真となる。[ 21 ]この関連で、ブランコ・グリュンバウムは、すべての面が単純サイクルであり、かつ任意の2つの面が互いに素であるか、または1つの辺のみを共有するような方法でスナークを曲面に埋め込むことはできないと予想した。もしスナークがそのような埋め込みを持っていたとしたら、その面はサイクル二重被覆を形成するだろう。しかし、マルティン・コホルはグリュンバウムの予想に対する反例を発見した。[ 22 ]
与えられた循環的に 5 連結な立方体グラフが 3 辺彩色可能かどうかを判定することはNP 完全である。したがって、グラフがスナークであるかどうかを判定することはco-NP 完全である。[ 23 ]
WT Tutte は、すべてのスナークがピーターセン グラフをマイナーとして持つと予想しました。つまり、最小のスナークであるピーターセン グラフは、他の任意のスナークからいくつかの辺を縮約し、他の辺を削除することによって形成できると予想しました。同等に (ピーターセン グラフの最大次数が 3 であるため)、すべてのスナークは、ピーターセン グラフのいくつかの辺を細分化することによって形成できる部分グラフを持ちます。この予想は、ピーターセン グラフをマイナーとして含むグラフは非平面でなければならないため、4 色定理の強化された形式です。1999 年に、 Neil Robertson、Daniel P. Sanders、Paul Seymour、およびRobin Thomas は、この予想の証明を発表しました。[ 24 ]この結果へのステップは 2016 年と 2019 年に発表されましたが、[ 25 ] [ 26 ]完全な証明は未発表のままです。[ 19 ]グラフ彩色とグラフマイナーに関連するその他の問題と結果については、ハドウィガー予想を参照してください。
タットはまた、任意のグラフへの一般化を予想した。すなわち、ペーターセン小節を持たないブリッジのないグラフには、どこにもゼロのない4-フローが存在する。つまり、グラフのエッジには方向と集合{1, 2, 3}からの数値を割り当てることができ、各頂点における入ってくる数値の合計から出ていく数値の合計を引いた値が4で割り切れる。タットが示したように、3次グラフの場合、このような割り当てが存在するのはエッジを3色で着色できる場合のみであり、この場合、この予想はスナーク予想から導かれる。しかし、スナーク予想を証明しても、3次グラフ以外のグラフにおける4-フローの存在という問題は解決しない。[ 27 ]
