彩色多項式

$k$-頂点彩色 $c\colon V\to\{1,\dots,k\}$ に、空でない色類 $c^{-1}(s)$ 全体からなる分割 $\pi(c)$ と、各ブロックにその色を対応させる写像を対応させる。彩色 の命題「適正彩色と独立な色類」により、各色類は独立集合であり、異なるブロックには異なる色が付くので、ブロックから色への写像は単射である。逆に、$V$ の $j$ 個の空でない独立集合への分割と、ブロックの集合から $\{1,\dots,k\}$ への単射が与えられれば、各頂点にそのブロックの色を付けることで $k$-頂点彩色が得られる（同じ命題）。2 つの対応は互いに逆である。
$j$ 個のブロックから $k$ 色への単射は $k^{\underline j}$ 個あるので、分割のブロック数 $j$ ごとに数えて
$$ P_G(k)=\sum_{j=1}^na_j(G)\,k^{\underline j} $$
を得る。右辺は $k$ の整数係数の多項式である。$a_n(G)=1$（$n$ 個のブロックへの分割は 1 点集合への分割だけで、1 点集合は独立）であり、$k^{\underline n}$ だけが $k^n$ を含むので、次数は $n$、最高次の係数は $1$ である。
$k^{\underline j}>0$ と $j\le k$ は同値なので、$P_G(k)>0$ は「$j\le k$ かつ $a_j(G)>0$ となる $j$ がある」ことと同値である。$a_j(G)>0$ なら $G$ は $j$ 色で塗れるので $j\ge\chi(G)$ である。逆に $\chi(G)$ 色の彩色では空の色類がない（あれば $\chi(G)-1$ 色で塗れる）ので $a_{\chi(G)}(G)>0$ である。よって最小の $j$ は $\chi(G)$ であり、主張が従う。$\square$

正の整数 $k$ を固定する。$G-e$ の $k$-頂点彩色 $c$ を、$c(u)\ne c(v)$ のものと $c(u)=c(v)$ のものに分ける。
$c(u)\ne c(v)$ のものは、辺 $e$ の条件も満たすので、ちょうど $G$ の $k$-頂点彩色である。
$c(u)=c(v)$ のものは $G/e$ の $k$-頂点彩色と一対一に対応する。実際、$c$ に対し、$z$ に共通の色 $c(u)$ を付け、ほかの頂点の色はそのままにした写像 $c'$ を考える。$G/e$ の辺は、$G-e$ の $u,v$ を含まない辺か、$G-e$ の辺 $uw$ または $vw$ から来た辺 $zw$ である。前者の両端の色は $c$ で異なり、後者では $c'(z)=c(u)=c(v)$ が $c(w)$ と異なる。よって $c'$ は $G/e$ の彩色である。逆に $G/e$ の彩色 $c'$ から $c(u)=c(v)=c'(z)$ とおけば同じ理由で $G-e$ の彩色が得られ、2 つの対応は互いに逆である。
以上より $P_{G-e}(k)=P_G(k)+P_{G/e}(k)$ がすべての正の整数 $k$ で成り立つので、多項式として等しい。$\square$

1 と 2．$m$ についての帰納法で示す。$m=0$ なら $P_G=k^n$、$c=n$ なので、$b_n=1$ でほかの $b_j$ は $0$ であり、主張が成り立つ。
$m\ge1$ とし、辺 $e=uv$ をとる。$G-e$ は $n$ 頂点 $m-1$ 辺で、連結成分は $c$ 個（$e$ が橋でないとき）か $c+1$ 個（橋のとき）である。$G/e$ は $n-1$ 頂点で、$u,v$ の共通の隣接頂点の個数を $s$ とすると辺は $m-1-s$ 本であり、連結成分は $c$ 個である（$u,v$ は同じ成分にあり、つぶしても成分のつながり方は変わらない）。帰納法の仮定により
$$ P_{G-e}(k)=\sum_j(-1)^{n-j}b'_jk^j,\qquad P_{G/e}(k)=\sum_j(-1)^{n-1-j}b''_jk^j $$
と書けて、$b'_j,b''_j$ は 1・2 を満たす（$b''_n:=0$）。thm-cp-deletion-contraction により
$$ P_G(k)=\sum_j(-1)^{n-j}\bigl(b'_j+b''_j\bigr)k^j $$
なので $b_j=b'_j+b''_j\ge0$ である。$b_n=1+0=1$、$b_{n-1}=(m-1)+1=m$ である（$b''_{n-1}$ は $n-1$ 頂点のグラフ $G/e$ の最高次の係数 $1$）。$c\le j\le n-1$ では $G/e$ が $c$ 個の成分と $n-1$ 個の頂点をもつので $b''_j>0$、したがって $b_j>0$ である。$j< c$ では、$G-e$ の成分の個数は $c$ 以上なので $b'_j=0$、$b''_j=0$ であり、$b_j=0$ である。
3．Heron–Rota–Welsh予想 の定理「彩色多項式と特性多項式」により
$$ P_G(k)=\sum_{A\subset E}(-1)^{|A|}k^{\,c(A)} $$
である。ここで $c(A)$ はグラフ $(V,A)$ の連結成分の個数である。$k^{n-2}$ の係数に寄与するのは $c(A)=n-2$ となる $A$ である。$(V,A)$ の辺をもつ成分を考えると、$c(A)=n-2$ は「辺をもつ成分が 3 頂点の成分 1 つだけ」か「2 頂点の成分がちょうど 2 つ」のどちらかであることと同値である（辺をもつ成分の頂点数を $s_1,\dots,s_r$ とすると $c(A)=n-\sum_i(s_i-1)$）。前者では $A$ は 3 頂点の上の連結な単純グラフの辺集合なので、2 本の辺か三角形の 3 辺である。後者では $A$ は端点を共有しない 2 本の辺である。よって $c(A)=n-2$ となる $A$ は、任意の 2 本の辺（$\binom m2$ 個、符号 $+$）と三角形の 3 辺（$t$ 個、符号 $-$）であり、$k^{n-2}$ の係数は $\binom m2-t$ である。$(-1)^{n-(n-2)}=1$ なので $b_{n-2}=\binom m2-t$ である。$\square$

1．$G\sqcup H$ の $k$-頂点彩色は、$G$ の彩色と $H$ の彩色の組と一対一に対応する。
2．共通部分の頂点集合を $S$ とし、$k\ge r$ を固定する。$S$ 上の写像 $\sigma\colon S\to\{1,\dots,k\}$ で単射なもの（$K_r$ の $k$-頂点彩色）を 1 つ固定し、$G_i$ の彩色で $S$ への制限が $\sigma$ になるものの個数を $N_i(\sigma)$ とする。色の置換 $\rho$ は $G_i$ の彩色を $G_i$ の彩色に写し（彩色 の命題「色集合の単射による彩色の移送」）、制限が $\sigma$ のものを制限が $\rho\circ\sigma$ のものに一対一に写す。$S$ 上の単射どうしは色の置換で移り合うので、$N_i(\sigma)$ は $\sigma$ によらない。$G_i$ の彩色は $S$ への制限で分類できるので $P_{G_i}(k)=k^{\underline r}N_i$ である。
$G$ の写像 $c\colon V\to\{1,\dots,k\}$ が彩色であることは、$G_1$ と $G_2$ への制限がともに彩色であることと同値である（どの辺もどちらかに属するので）。よって $G$ の彩色は、$S$ 上の単射 $\sigma$ と、制限が $\sigma$ になる $G_1$・$G_2$ の彩色の組に一対一に対応し、
$$ P_G(k)=k^{\underline r}N_1N_2=\frac{P_{G_1}(k)P_{G_2}(k)}{k^{\underline r}} $$
である。$k^{\underline r}=P_{K_r}(k)$ を掛けて分母を払うと、$k\ge r$ のすべての整数で主張の等式が成り立つので、多項式として等しい。$\square$

準備．向き付けで、向きに沿って進み出発点に戻る長さ $1$ 以上の道筋（有向閉歩道）があれば、有向閉路がある。実際、長さ最小の有向閉歩道をとると、途中で同じ頂点を 2 度通れば、その間の部分がより短い有向閉歩道になるので、頂点はすべて相異なる。単純グラフにはループがなく、2 頂点の間の辺は 1 本で向きは 1 つなので、長さは $1$ でも $2$ でもなく、3 以上である。
漸化式．$\alpha(G)=\alpha(G-e)+\alpha(G/e)$ を示す。$e=uv$ とし、$G-e$ の非巡回な向き付け $O$ に $u\to v$ を加えたものを $O_1$、$v\to u$ を加えたものを $O_2$ とする。$O_1$ の有向閉路は $O$ が非巡回なので $u\to v$ を通り、残りは $O$ の $v$ から $u$ への有向道である。逆にそのような有向道があれば $O_1$ は有向閉路をもつ。よって $O_1$ が非巡回であることは、$O$ に $v$ から $u$ への有向道がないことと同値であり、$O_2$ についても $u$ と $v$ を入れ換えて同様である。$O$ に $u$ から $v$ への有向道と $v$ から $u$ への有向道が両方あれば、つないで有向閉歩道ができ、準備により $O$ は非巡回でない。したがって $O_1,O_2$ の少なくとも一方は非巡回であり、両方が非巡回になるのは、$O$ に $u,v$ 間の有向道がどちらの向きにもないときである。$G$ の非巡回な向き付けは $e$ を除けば $G-e$ の非巡回な向き付けになるので、
$$ \alpha(G)=\alpha(G-e)+N,\qquad N=\#\{O: u,v\text{ 間に有向道のない }G-e\text{ の非巡回な向き付け}\} $$
である。
$N=\alpha(G/e)$ を示す。$O$ を $N$ に数える向き付けとする。$u,v$ の共通の隣接頂点 $w$ について、$u\to w\to v$ も $v\to w\to u$ も有向道になるので、$uw$ と $vw$ はともに $w$ に向かうか、ともに $w$ から出る。そこで $G/e$ の向き付け $O'$ を、$u,v$ を含まない辺はそのままに、辺 $zw$ は $G-e$ の辺 $uw$ または $vw$ と同じ向きに（$u,v$ を $z$ に読み替えて）定める。$O'$ に有向閉路があるとする。$z$ を通らなければそれは $O$ の有向閉路である。$z$ を通るなら $z\to w_1\to\cdots\to w_r\to z$ と書け、$O$ では $x\to w_1\to\cdots\to w_r\to y$（$x,y\in\{u,v\}$）となる。$x=y$ なら $O$ の有向閉歩道、$x\ne y$ なら $u,v$ 間の有向道であり、どちらも $O$ の選び方に反する。よって $O'$ は非巡回である。
逆に $G/e$ の非巡回な向き付け $O'$ から、$G-e$ の向き付け $O$ を、$z$ を含む辺 $zw$ の向きを、それから来た辺 $uw$・$vw$ に写して定める。$O$ の有向閉路、または $u$ から $v$（あるいは $v$ から $u$）への有向道があれば、$u,v$ を $z$ に置き換えると、$O'$ の長さ $1$ 以上の有向閉歩道になる（有向道の長さは $2$ 以上である。$uv$ は $G-e$ の辺でないから）。準備によりこれは $O'$ が非巡回であることに反する。よって $O$ は $N$ に数えられ、2 つの対応は互いに逆である。
結論．$m$ についての帰納法で示す。$m=0$ なら向き付けは 1 通りで、$(-1)^nP_G(-1)=(-1)^n(-1)^n=1$ である。$m\ge1$ なら、thm-cp-deletion-contraction と、$G/e$ の頂点数が $n-1$ であることから
$$ (-1)^nP_G(-1)=(-1)^nP_{G-e}(-1)+(-1)^{n-1}P_{G/e}(-1)=\alpha(G-e)+\alpha(G/e)=\alpha(G) $$
である。$\square$

1．thm-cp-coefficients の記法で $(-1)^nP_G(q)=\sum_jb_j(-1)^{2n-j}q^j=\sum_jb_j|q|^j$ であり、$b_j\ge0$、$b_n=1$ なので、この和は $|q|^n>0$ 以上である。
2．thm-cp-coefficients の 2 により、$P_G$ の $0$ でない最低次の項は $k^c$ の項である。
3．辺の数 $m$ についての帰納法で示す。$m=0$ なら $P_G=q^n$、$c=n$ で正である。$m\ge1$ とし、辺 $e=uv$ をとる。
$e$ が橋でないとき、$G-e$ は $n$ 頂点 $c$ 成分、$G/e$ は $n-1$ 頂点 $c$ 成分で、どちらも辺が少ない。thm-cp-deletion-contraction により
$$ (-1)^{n-c}P_G(q)=(-1)^{n-c}P_{G-e}(q)+(-1)^{(n-1)-c}P_{G/e}(q) $$
で、右辺の 2 項は帰納法の仮定により正である。
$e$ が橋のとき、まず $q\,P_G(q)=(q-1)P_{G-e}(q)$ を示す。正の整数 $k$ を固定する。$G-e$ で $v$ を含む成分を $H$、残りを $H'$ とすると、$u$ は $H'$ にあり、prop-cp-gluing の 1 の対応で $G-e$ の彩色は $H$ と $H'$ の彩色の組である。色の置換は $H$ の彩色を $H$ の彩色に写すので、$v$ の色が $a$ である $H$ の彩色の個数は $a$ によらず $P_H(k)/k$ である。したがって $c(u)=c(v)$ となる $G-e$ の彩色は $P_{G-e}(k)/k$ 個あり、$P_G(k)=P_{G-e}(k)-P_{G-e}(k)/k$ である。$G-e$ は $n$ 頂点 $c+1$ 成分なので、帰納法の仮定から
$$ (-1)^{n-c}P_G(q)=\frac{1-q}{q}\,(-1)^{n-(c+1)}P_{G-e}(q)>0 $$
である。
4．$P_G(1)$ は 1 色での彩色の個数であり、辺があれば $0$、なければ $1$ である。$\square$