4-リスト彩色不可能な平面グラフ
どんな平面グラフも4彩色*1可能という事実は、四色定理という名で広く知られています。では、4彩色を少し拡張した概念である、4リスト彩色については任意の平面グラフに対して可能なのか？というのが今回の話です。
まず、リスト彩色とは以下のように定義されます。
定義（リスト彩色）
グラフ$G=(V,E)$の各頂点$v\in V$に対して色の集合（リスト）$S_v$が与えられたとする。このとき、各頂点$v\in V$の色をリスト$S_v$から選んで塗り、隣り合う頂点が異なる色で塗られているとき、これをリスト$S_v$を用いた彩色とよぶ。各頂点$v\in V$に対して大きさ$k$であるどんなリスト$S_v(\forall v\in V\ |S_v|=k)$が与えられても、$G$が$S_v$を用いて彩色できるとき、$G$は$k-$リスト彩色可能、または$k-$選択可能*2という。
通常の彩色では、すべての頂点について同じ色の集合から色を選んで塗りますが、リスト彩色では頂点ごとに選ぶ色の集合を変えることを考えます。$k-$リスト彩色可能なグラフはすべての頂点に同じ$k$色の集合を与えられてもその集合から色を選んで彩色できる（つまり通常の彩色ができる）ので、彩色よりもリスト彩色のほうが強い概念です。
しかし、直感的には頂点ごとに選ぶ色の集合を変えたほうが彩色しやすくなるのではないか、$k-$彩色が可能なグラフは$k-$リスト彩色も可能なのではないか、と思ったりもするかもしれません。
実際、任意の平面グラフは5彩色可能ですが、5-リスト彩色も可能です。
しかし、四色定理のリスト彩色版は実は成り立ちません。つまり、4-リスト彩色不可能な平面グラフが存在するのです！
4-リスト彩色不可能な平面グラフの例は色々ありますが、その中でも比較的頂点数が少ないシンプルなもの（といっても63頂点ありますが）を以下で紹介します。Mirzakhani graph*3 と呼ばれるグラフです。
上のほうに1つだけポツンとある頂点からは、各正方形の真ん中の頂点（次数4の頂点）を除いたすべての頂点に辺がのびています。このグラフが平面グラフであることはすぐに確認できます。では、Mirzakhani graphが4-リスト彩色可能でないことを実際に確認していきましょう。
Mirzakhani graphの各頂点に下図のような色（色は数字で表すことにします）のリストを与えます。ただし、$L_i=\{1,2,3,4,5\}\setminus \{i\}$とします。
このリストを用いた彩色が不可能なことを示します。
上のほうに1つだけポツンとある頂点（最大次数頂点）の色が1であったとします。このとき、正方形の中心にある頂点のリストが$L_1$であるような5つの正方形（とその中心）からなる部分グラフをとってきます（左下図）。
この部分グラフの頂点に、右上図のように名前をつけます。
まず、正方形の中心の頂点のリストはすべて$L_1$なので、正方形の4つの角にある頂点が2,3,4,5すべてを網羅すると中心の頂点が塗れなくなります。また、正方形の4つの角にある頂点は最大次数頂点に隣接しているので、1で塗ることはできません（この事実は以降暗黙のうちに使っていきます）。ゆえに、正方形の4つの角にある頂点のうち同じ色で塗られている2頂点が少なくとも1組あります。
ここで、ある1直線にならんだ5頂点のうちの正方形の中心を除いた3頂点（例えばb,d,hなど）をすべて同じ色で塗ると矛盾することを示します。例えばb,d,hが同じ色で塗られたとします。b,d,hの色のリストはそれぞれ$L_2,L_3,L_5$なので、b,d,hを同じ色で塗るには4で塗るしかありません。このとき真ん中の正方形に着目すると、kのリストは$L_4$なのでd,kを同じ色で塗ることはできません。よってe,iが同じ色で塗られることになります。e,iのリストは$L_5,L_2$で、4で塗られたdに隣接しているので、e,iの色は3となります（下図）。
ここで右と下の正方形に着目すると、n,qのリストは$L_3$なのでn,qは3で塗ることができません。よってlとk、kとpが同じ色で塗られることになり、つまりl,k,pが同じ色で塗られることになります。l,k,pのリストは$L_2,L_4,L_5$なので、l,k,pを同じ色で塗るには3で塗るしかありません。しかしこれでは同じ色の頂点が隣接するので矛盾します。
ほかの1直線上にならんだ5頂点のうち正方形の中心を除いた3頂点をすべて同じ色で塗っても、同様に矛盾が示せます。
よって、以下では上で考えたような3頂点がすべて同じ色で塗られる場合は除いて考えます。まず、左の正方形に着目して、aとeが同じ色で塗られているとします。このとき、下の正方形に着目します。eとnが同じ色で塗られるとすると、上で考えたような組み合わせの3頂点がすべて同じ色で塗られることになるのでダメで、ゆえにlとkが同じ色で塗られていることになります。同様に右の正方形と上の正方形にも着目すると、iとq、dとhが同じ色で塗られていることになります（下図）。
ここで、真ん中の正方形に着目すると、dとk、eとiのうち少なくともどちらかが同じ色で塗られている必要があります。dとkが同じ色で塗られていたとすると、l,k,d,hがすべて同じ色で塗られていることになります。しかしl,k,d,hのリストは$L_2,L_4,L_3,L_5$なので、l,k,d,hを同じ色で塗るには1で塗る必要があり、これは1で塗られている最大次数頂点と隣接していることと矛盾します。
左の正方形でbとdが同じ色で塗られている場合も同様に矛盾を示すことができます。よって、最大次数の頂点の色が1である場合は彩色できないことが示されました。
最大次数の頂点の色が2,3,4の場合も、中心の頂点のリストが$L_2,L_3,L_4$であるような正方形からなる部分グラフをとってきて、同じような議論をすれば矛盾を示せます。
よって、上で与えたようなリストを用いてMirzakhani graphは彩色できないので、Mirzakhani graphは4-リスト彩色不可能であることが示されました。
ちなみに、Mirzakhani graphは3彩色も可能な平面グラフです（各正方形の真ん中の頂点と、上に一つだけある頂点をすべて同じ色で塗って、残りは偶数長閉路なので2色で塗れる）。3彩色可能なのに4-リスト彩色はできないというのは直感に反して面白いですね。
