彩色数

頂点集合 $S$ の部分集合のうち独立集合であるもの（空集合を含む）の個数を $I(S)$ とすると、すべての頂点を覆う $k$ 個の独立集合の組の個数は、包除原理で $\sum_S (-1)^{N - \lvert S \rvert} I(S)^k$ と書けます。これが $0$ でない最小の $k$ が彩色数です。 $I(S)$ は、 $S$ の頂点 $v$ を 1 つ選んで「 $v$ を使わない」「 $v$ を使い、 $v$ とその隣を除いた中から残りを選ぶ」に分けると、全体で $O(2^N)$ で求まります。 $N$ は 20 程度までが目安です。

• chromatic_number(n, edges): 頂点数 $n$ と無向辺のリスト edges = [(u, v), ...]（自己ループなし）のグラフの彩色数。 $n = 0$ なら $0$、辺がなければ $1$。 $O(2^N N)$

和はとても大きくなるので、2 つの素数 $998244353$ と $10^9 + 7$ を法として計算し、どちらかで $0$ でなければ $k$ 色で塗れると判定します。本当の値が $0$ でないのに両方の素数の倍数になってしまうと答えを大きく間違えますが、ほとんど起こりません。

例（5 頂点の閉路は 3 色必要）:

print(chromatic_number(5, [(i, (i + 1) % 5) for i in range(5)]))  # 3

コード

def chromatic_number(n, edges):
    # 頂点 0..n-1、無向辺 edges = [(u, v), ...] のグラフの彩色数（自己ループなし）
    if n == 0:
        return 0
    adj = [0] * n
    for u, v in edges:
        adj[u] |= 1 << v
        adj[v] |= 1 << u
    # ind[S] = S の部分集合のうち独立集合であるものの個数（空集合を含む）
    ind = [1] * (1 << n)
    pc = [0] * (1 << n)
    for S in range(1, 1 << n):
        b = S & -S
        v = b.bit_length() - 1
        # v を使わないものと、v を使う（v とその隣を除いた中から選ぶ）もの
        ind[S] = ind[S ^ b] + ind[S & ~(adj[v] | b)]
        pc[S] = pc[S ^ b] + 1
    # k 色で塗れるのは sum((-1)^(n - |S|) * ind[S]^k) が 0 でないとき
    pos = [ind[S] for S in range(1 << n) if (n - pc[S]) % 2 == 0]
    neg = [ind[S] for S in range(1 << n) if (n - pc[S]) % 2 == 1]
    res = n
    # 2 つの素数を法として計算し、どちらかで 0 でなければ塗れるとする
    for p in (998244353, 1000000007):
        a, b = pos[:], neg[:]
        for k in range(1, res):
            if (sum(a) - sum(b)) % p:
                res = k
                break
            a = [x * y % p for x, y in zip(a, pos)]
            b = [x * y % p for x, y in zip(b, neg)]
    return res