Björklund's chromatic number algorithm in Python

Computes the chromatic number in O*(2^n) time by inclusion-exclusion over covers with independent sets.

File: bjorklund_chromatic_number.py, 45 lines
Level: I0 not checked yet
Toolchain: Python 3.14, pytest 9
Test framework: pytest
Run the tests: python3 -m pytest

bjorklund_chromatic_number.pyRaw GitHub

# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/bjorklund-chromatic-number/. The authors are listed in prov/X7DPRF.jsonl.

from collections.abc import Sequence


def bjorklund_chromatic_number(adj: Sequence[Sequence[int]]) -> int:
    """Return the chromatic number of a simple undirected graph.

    adj[v] lists the neighbours of v (vertices 0 .. n-1, each edge in both lists,
    no self-loops). Subsets of the vertices are bitmasks. f[S] becomes the number
    of independent sets contained in S, the empty set included, and the number of
    k-tuples of independent sets whose union is all of V is
    sum over S of (-1)^(n - |S|) f[S]^k. The answer is the least k for which
    this number is positive. Time O(2^n n^2) and space O(2^n n) words.
    """
    n = len(adj)
    if n == 0:  # @line L1
        return 0
    nbr = [0] * n
    for v in range(n):
        for w in adj[v]:
            nbr[v] |= 1 << w
    full = 1 << n
    f = [0] * full
    f[0] = 1
    for s in range(1, full):  # @line L2
        v = (s & -s).bit_length() - 1
        rest = s & (s - 1)
        f[s] = 1 if f[rest] and not (nbr[v] & rest) else 0  # @line L3
    for v in range(n):  # @line L4
        bit = 1 << v
        for s in range(full):
            if s & bit:
                f[s] += f[s ^ bit]  # @line L5
    sign = [1 if (n - bin(s).count("1")) % 2 == 0 else -1 for s in range(full)]
    power = [1] * full
    for k in range(1, n + 1):  # @line L6
        total = 0
        for s in range(full):
            power[s] *= f[s]
            total += sign[s] * power[s]  # @line L7
        if total > 0:  # @line L8
            return k
    return n  # unreachable: the n singletons always cover V

test_bjorklund_chromatic_number.py 53 lines

# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/bjorklund-chromatic-number/. The authors are listed in prov/X7DPRF.jsonl.

import itertools
import random

from bjorklund_chromatic_number import bjorklund_chromatic_number


def make(n: int, edges: list[tuple[int, int]]) -> list[list[int]]:
    adj: list[list[int]] = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
    return adj


def chi_brute(n: int, edges: list[tuple[int, int]]) -> int:
    for k in range(n + 1):
        for col in itertools.product(range(k), repeat=n):
            if all(col[u] != col[v] for u, v in edges):
                return k
    return n


def test_example() -> None:
    c5 = [(0, 1), (1, 2), (2, 3), (3, 4), (4, 0)]
    assert bjorklund_chromatic_number(make(5, c5)) == 3


def test_edges() -> None:
    assert bjorklund_chromatic_number([]) == 0
    assert bjorklund_chromatic_number([[]]) == 1
    assert bjorklund_chromatic_number(make(4, [])) == 1
    assert bjorklund_chromatic_number(make(2, [(0, 1)])) == 2
    k5 = list(itertools.combinations(range(5), 2))
    assert bjorklund_chromatic_number(make(5, k5)) == 5


def test_petersen() -> None:
    outer = [(i, (i + 1) % 5) for i in range(5)]
    spokes = [(i, i + 5) for i in range(5)]
    inner = [(5 + i, 5 + (i + 2) % 5) for i in range(5)]
    assert bjorklund_chromatic_number(make(10, outer + spokes + inner)) == 3


def test_random_against_brute_force() -> None:
    rng = random.Random(2009)
    for _ in range(600):
        n = rng.randint(0, 7)
        p = rng.random()
        edges = [e for e in itertools.combinations(range(n), 2) if rng.random() < p]
        assert bjorklund_chromatic_number(make(n, edges)) == chi_brute(n, edges)

What the next level needs

the tests did not run in this build

Read the full page about Björklund's chromatic number algorithm