あそびをせんとや

2001.02.27 公開
2026.06.21 更新

左にメニューが表示されていなければこのバナーをクリック →

X(twitter)をやっています　@AsobiSent パターンあやとりの世界というサイトを作っています 2024.05.22 公開 「数学セミナー」連載の「あやとりの楽しみ」のサポートページはこちら　 2026.06.15 更新　　update 　SUWAプレミアム認定製品のアクリルパズル パズル マスマティカのページを作りました　 2024.12.31 公開

ひとこと

6月21日(日)　グラフの彩色(その3)、庭に来たネコ

　(グラフ理論の)グラフの彩色の論文のご紹介です。

○

　一昨日からグラフの頂点彩色についてご紹介してきましたが、きっかけは arXiv で Exact 6-cut rigidity and small-order superconnectivity for the 6-regular case of Dirac's k=4 problem(Alper Ferudun：2026年6月)という論文を見たのがきっかけです。

　まず、この論文のもとになる Diracのk=4問題を理解する必要があります。Diracが1970年の論文で

k >= 4 のとき、critical edge（削ると彩色数が下がる辺）が 1 本もない k-vertex-critical グラフは存在するか？

　という open problem （未解決問題）を提起したのだそうです。kが5以上についてはそういうグラフは存在しないことが証明されているのだそうですが、k=4 についてはまだ解かれていないのだそうです。

　Diracの問題そのものの意味がわかりにくいので少し丁寧に説明してみます。（その準備として一昨日と昨日に完全グラフや完全二部グラフの頂点彩色の話をご紹介したのでした。）まず、存在を問われている 4-vertex-criticalグラフ（4-頂点臨界グラフ）というのは、頂点が４つのグラフではなくて、4-彩色可能なグラフであって、どの頂点を取り除いても、彩色数が3になってしまうようなグラフを指しています。（頂点を１つ取り除くときには、取り除かれる頂点に接続している辺もすべて一緒に取り除かれます。）

　問題の前半のcritical edge（削ると彩色数が下がる辺）が 1 本もない の「critical edge」とは、その辺（頂点ではなくてたった１本の辺）を取り除くと、グラフ全体の彩色数が減ってしまうような辺を指します。

　Dirac問題のk=4の場合というのを、回りくどく丁寧に説明してみるとこんな風になります。「頂点彩色数が4のグラフがある。このグラフの頂点は3色では塗分けられないが、このグラフからどの1頂点を取り除いても3色で塗分けられるようになる。このグラフからどの1辺を取り除いても、彩色数は4のままで減らない。そんなグラフは存在するだろうか？　それがあるなら実例を示し、ないならそれを証明せよ。」ということです。

　一昨日の完全二部グラフを例に考えてみましょう。

完全二部グラフの彩色

　これは 2-頂点臨界グラフではありません（頂点を１つ取り除いても彩色数は2のままで、彩色数1に減ったりしません）。一方で、どの1辺を取り除いても彩色数は2のままで変わりません。なので critical edge が存在しないグラフの例ではあります。

　完全グラフだったらどうでしょうか？

完全グラフの頂点の彩色

　こちらは逆に、k-頂点臨界グラフです。どの頂点を取り除いても彩色数はかならず減ります。完全グラフは頂点数＝彩色数で、頂点を1つ取り除いたグラフも完全グラフですから自明です。一方、任意の1つの辺を取り除くと、彩色数は必ず減ってしまいます。取り除いた辺の両側の頂点は同じ色にできるためです。

完全グラフ K4 から1辺を取り除いてみる

　完全グラフ K₄ は正四面体グラフですから、すべての辺は等価です。このように1辺を取り除くことで、彩色数を1つ減らせるのです。完全グラフは critical edge が1本もありませんが、でも頂点臨界グラフではないため Diracの問題の例にはなりません。

　一方、k=2 の場合、奇数のサイクルグラフ（円環状のグラフ）は彩色数は3になりますが、1辺を取り除くとパスグラフ（枝分かれもサイクルもないグラフ）になって、彩色数は2になります。

5-サイクルグラフから1辺を取り除いて 5-パスグラフにする

　つまり、奇数のサイクルグラフは2-臨界頂点グラフであって、かつすべての辺が critical edge なのです。

　この論文は、未解決の k=4 の場合について、6-正則（すべての頂点の次数：頂点につながる辺の数が6であるグラフ）な k-臨界頂点グラフを調べて、少なくとも頂点数が15までのグラフにはDiracの問題に該当するグラフは存在しないことを計算機の探索で調べた、というのが第1の結果です。（第2、第3の結果はかみくだいて説明するのが大変なので省略します。）

　で、それを調べる中で n=13 でちょっとおもしろいグラフが見つかった、というのがご紹介した13頂点のグラフだったのです。何が珍しいかと言うと、4-臨界頂点グラフであり（どの頂点を取り除いても彩色数が3になる）、13本の辺は critical edge (取り除くと3彩色になってしまう)けれど、それ以外の辺は取り除いても彩色数が減らない辺になっている、というのが「おもしろい」のです。

　その「おもしろい」ところをまずは実感してみようということでグラフを作って手で塗分けてみて「なるほど」と思ったのでご紹介したのでした。

○

　ちなみに昨日から掲載している対称性の高いこのきれいなグラフですが、

　この図そのものが論文に載っているわけではなく、論文では L?bFFbw~B{FwFw という文字列で表現されています。

　私は最初にざっとこの論文を見渡してみたとき「何らかのトラブルで文字化けしているのだろうか？」と邪推したのですが、そうではなくてこれは graph6形式 と呼ばれる、計算機でグラフを表現するアスキーコード表現のフォーマットでの表記だということがわかりました。これを可視化するツールがいろいろあるらしいので調べてみて表記の図を作ったのでした。

○

　先月、土曜日だったかの早朝に庭の木の枝を落として、その枝をごみとして出すために細かくする作業をしていたときに、近くでその作業をずっと眺めていたネコがいたのです。毛足の長いネコでした。

庭に来たネコ

　一時間ほどたったあたりで軽く声をかけてみたら、驚いたことに近づいてきて足にまとわりつく動作をしてくれました。びっくりです。こんなに警戒心がなくて大丈夫だろうかと心配になりました。

すり寄ってきてくれた

　ネコは好きなので、しゃがんでなでさせてもらいました。びっくりしたことに転がっておなかまでなでさせてもらいました。

なでさせてくれた

　おそらく近所の飼い猫だと思うのですが、それ以来うちの庭でみかけたことがなくて、どうしたかなあと思っています。ひどい目にあっていなければいいなと思っていたのですが、先週だったか、車ででかけたとき、近くの神社あたりでこの猫を見かけました。元気な様子で安心しました。

＜おまけのひとこと＞
　昨日はひどい雨でしたが今朝は晴れています。