グラフ理論の問題
を整数とする。頂点集合を とし、相異なる 2 頂点 を
のときに限り辺で結んだ単純無向グラフを とする（閉路 の 2 乗グラフ）。 の彩色数（隣接する頂点が異なる色になるように頂点を塗るのに必要な最小の色数）を 、辺彩色数（同じ頂点を端点にもつ辺が異なる色になるように辺を塗るのに必要な最小の色数）を とする。
の値を求めよ。
この問題で使うもの
- 頂点彩色と彩色数（説明と入口の問題）
- 辺彩色数とヴィジングの定理（説明と入口の問題）
- グラフの次数と握手補題（説明と入口の問題）
- 最大独立集合と最小頂点被覆（説明と入口の問題）
この問題を解けるようになるまで（11 技能）
読み込み中…
右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。
ヒント
行き詰まったら、上から順に 1 つずつ開いてください。
ヒント 1
は が の倍数かどうか、 は が奇数か偶数かで場合分けして考える。 のとき が何になるかにも注意する。
ヒント 2
彩色数の下界には独立数 と を使う。辺彩色数は、奇数頂点の正則グラフではマッチングが 本以下であることを、偶数の では辺集合を偶閉路に分割できることを使う。
ヒント 3
なら 、 かつ なら （色 と のブロックを並べる）。 が奇数なら 。 は差 、差 の辺がそれぞれ偶閉路になる。 は偶閉路への分割を具体的に作る。
答えと解説
答えを見る
どこでつまずきましたか？（選ぶと、戻る場所を案内します）
解説を読む
準備. なので は法 で互いに異なり、 は -正則な単純グラフで、辺の数は である。特に では が 以外のすべての剰余を表すので である。
彩色数.
(i) ： より 。
(ii) （）： は三角形なので 。頂点 に色 を塗ると、距離 の頂点は を法として異なり、 なので と のつなぎ目でも矛盾しない。よって 。
(iii) , （）：独立集合の頂点を巡回的に並べると、隣り合う 2 頂点の間隔は 以上でなければならない。 頂点の独立集合では間隔の和が なので 、すなわち独立数 。各色のクラスは独立集合なので 、よって 。一方、 と書き、頂点を順に「」のブロック 個、「」のブロック 個で塗ると、どのブロックの境目（つなぎ目 を含む）でも距離 以内の頂点の色は異なる。具体的には
- ：
- ：
- ：
- ：
よって 。
辺彩色数. 最大次数は なので 、ヴィジングの定理より 。
(iv) が奇数（）：各色のクラスはマッチングで、頂点数が奇数なので高々 本の辺しか含まない。 色では高々 本しか塗れないので 。
(v) ：差 の辺は長さ （偶数）の閉路をなし、差 の辺は偶数の頂点と奇数の頂点それぞれの上で長さ （、偶数）の閉路 2 つをなす。偶閉路は 2 色で辺彩色できるので、合計 色で塗れる。よって 。
(vi) ： の辺は、閉路 と閉路 （いずれも長さ ）に分割される（12 本の辺がちょうど 1 回ずつ現れることが確かめられる）。各偶閉路を 2 色で塗れば 色で済むので 。
(vii) ：閉路 （長さ ）を取り除くと、残りの辺 は閉路 （長さ ）と閉路 （長さ ）になる。すべて偶閉路なので、前者を色 、後の 2 つを色 で交互に塗ればよく、。
まとめ.
の和は 、 の和は 。よって 。
別解
は 4-正則グラフである。 のときは 、 のときは から完全マッチングを除いたグラフである。
【彩色数】
- : なので 。
- （）: 頂点を で塗ればよい。同じ色の頂点の差は の倍数なので隣接しない。 は三角形 を含むから 。
- それ以外（）: 独立集合の大きさは高々 である。 では なので 。 では なので 。一方、色クラスを 3 個おき（または 2 個おきを混ぜた）の連続ブロックに分ければ 4 色で塗れる。よって 。
の和は 。
【辺彩色数】
なので 。
- が奇数（）: 1 色あたりの辺は高々 本。辺は 本あり、 なので 4 色では足りない。ヴィジングの定理より だから 。
- が偶数（）: 偶数位数の巡回群上のケーリーグラフ（アーベル群上の偶数位数の正則ケーリーグラフ）は第 1 種であるという既知の結果を用いる。これより 。（この既知の結果は証明せず引用した。 などの個別の彩色は構成して確かめていない。）
の和は 。
。