Chromatic Polynomial — Graph Coloring Polynomial

July 2026 · 22 min read

What Is the Chromatic Polynomial?

Given a simple graph G = (V, E) and a positive integer k, a proper k-coloring assigns one of k colors to every vertex so that no two adjacent vertices share the same color. The chromatic polynomial P(G, k) is the function that counts the number of distinct proper k-colorings of G.

Why does this matter in competitive programming?

• P(G, k) encodes all coloring information in a single algebraic object.
• Evaluating P(G, k) at specific values answers questions like "How many ways to 3-color this graph?"
• The smallest positive integer k where P(G, k) > 0 is the chromatic number χ(G).
• Many inclusion-exclusion and Möbius-inversion techniques in combinatorics connect to chromatic polynomials.

Quick Examples

Empty graph E_n (n vertices, no edges):

Every vertex can be colored independently, so P(E_n, k) = kⁿ.

Complete graph K_n:

The first vertex has k choices, the second has k−1, and so on. P(K_n, k) = k(k−1)(k−2)⋯(k−n+1) = k⁽ⁿ⁾ (the falling factorial).

Single edge K₂:

P(K₂, k) = k(k−1) = k² − k.

Tree T_n on n vertices:

Root the tree and color greedily: the root has k choices, every other vertex has k−1 (it only needs to avoid its parent's color). So P(T_n, k) = k(k−1)ⁿ⁻¹.

Cycle C_n:

P(C_n, k) = (k−1)ⁿ + (−1)ⁿ(k−1). For the triangle C₃ this gives (k−1)³ − (k−1) = k³ − 3k² + 2k = k(k−1)(k−2), confirming P(K₃, k).

Deletion-Contraction

The fundamental recursive identity for computing chromatic polynomials is the deletion-contraction recurrence. Pick any edge e = {u, v} of G:

Here:

• G − e ("deletion"): the graph obtained by removing edge e. This counts colorings where u and v may or may not share a color.
• G / e ("contraction"): the graph obtained by contracting edge e (merging u and v into a single vertex, removing duplicated edges). This counts the "over-counted" colorings where u and v share the same color.

The subtraction removes exactly those colorings of G − e where u and v get the same color — leaving only proper colorings of G.

Base Cases

• If G has no edges, then P(G, k) = kⁿ where n = |V(G)|.
• If G has a loop (self-edge), then P(G, k) = 0 — no proper coloring exists.
• If G is the complete graph K_n, return the falling factorial directly.

Worked Example: Path P₃

Consider the path graph on vertices {1, 2, 3} with edges {1,2} and {2,3}.

Step 1: Delete-contract on edge {1, 2}:

• G − {1,2}: vertices {1,2,3} with only edge {2,3}. This is K₂ plus an isolated vertex. P = k · k(k−1) = k²(k−1).
• G / {1,2}: merge vertices 1 and 2 into vertex "12", edges become {12, 3}. This is K₂. P = k(k−1).

Step 2: Combine:

P(P₃, k) = k²(k−1) − k(k−1) = k(k−1)[k − 1] = k(k−1)².

This matches the tree formula k(k−1)ⁿ⁻¹ with n = 3. ✓

Worked Example: Cycle C₄

Label the cycle 1–2–3–4–1. Delete-contract on edge {1, 2}:

• G − {1,2}: the path 1–4–3–2. P(path of 4) = k(k−1)³.
• G / {1,2}: merge 1 and 2 into "12". Edges {12,3}, {3,4}, {4,12} form a triangle C₃ = K₃. P = k(k−1)(k−2).

Therefore:

P(C₄, k) = k(k−1)³ − k(k−1)(k−2) = k(k−1)[(k−1)² − (k−2)] = k(k−1)(k² − 3k + 3).

Plugging k = 3: 3 · 2 · 3 = 18 proper 3-colorings. You can verify this by enumeration.

Chromatic Polynomials of Common Graphs

Knowing closed-form chromatic polynomials for standard graph families saves enormous work in contests.

Complete Graph K_n

P(K_n, k) = k(k−1)(k−2)⋯(k−n+1) = k⁽ⁿ⁾.

Derivation: In K_n every pair of vertices is adjacent, so each vertex must receive a unique color. Vertex 1 has k choices, vertex 2 has k−1, …, vertex n has k−n+1.

Tree T_n

P(T_n, k) = k(k−1)ⁿ⁻¹.

Derivation: Root the tree at any vertex. The root has k color choices. Every non-root vertex has exactly one parent, and it must only differ from its parent's color, giving k−1 choices. By the multiplication principle, the total is k · (k−1)ⁿ⁻¹. Note this works for any tree — the structure beyond the parent-child relationship doesn't matter because trees have no cycles.

Cycle C_n

P(C_n, k) = (k−1)ⁿ + (−1)ⁿ(k−1).

Derivation via deletion-contraction: Pick any edge e in C_n. Deleting e produces a path P_n, which is a tree: P(P_n, k) = k(k−1)ⁿ⁻¹. Contracting e produces C_n−1. So P(C_n, k) = k(k−1)ⁿ⁻¹ − P(C_n−1, k). Unrolling this recurrence with P(C₃, k) = k(k−1)(k−2) as the base gives the closed form.

Alternative derivation (transfer matrix): Color vertex 1 with any of k colors. Vertices 2, 3, …, n−1 each avoid only their predecessor (k−1 choices each). Vertex n must avoid both vertex n−1 and vertex 1. Splitting into cases on whether vertex n−1 matches vertex 1 yields the same formula.

Complete Bipartite Graph K_a,b

P(K_a,b, k) = Σ_i=0^a Σ_j=0^b (−1)^a+b−i−j C(a, i) C(b, j) (i + j = total distinct colors used).

A simpler formulation uses the fact that all vertices in one part must differ from all in the other:

P(K_a,b, k) = Σ_j=0^min(a,b) (−1)^j C(b, j) · k^(a) · (k − a)^(b−j) ... (via inclusion-exclusion on shared colors).

For the practical special case K_2,3:

P(K_2,3, k) = k(k−1) · [(k−2)³ + correction terms from IE] = k⁵ − 6k⁴ + 14k³ − 16k² + 9k − 2.

Inclusion-Exclusion Approach

Deletion-contraction is intuitive but slow. For algorithmic computation, inclusion-exclusion over independent sets (or equivalently, over edge subsets) provides a more structured approach.

Whitney's Rank Polynomial

Whitney (1932) showed that the chromatic polynomial can be written as an alternating sum over all subsets A ⊆ E of the edge set:

Intuition: start with kⁿ (all colorings ignoring edges), then use inclusion-exclusion to subtract colorings that violate at least one edge, add back those violating at least two, etc. Each subset A forces the endpoints of every edge in A to share a color, effectively merging those endpoints — the number of "free" color choices is k^c(A).

The Broken Circuit Theorem

Fix a total ordering on the edges of G. A broken circuit is a cycle with its largest edge removed. Whitney's broken circuit theorem states:

This theorem is primarily a theoretical tool: it shows that chromatic polynomial coefficients alternate in sign and gives a combinatorial interpretation of each coefficient. In practice, it's less useful for computation than the bitmask DP approach we'll see next.

Connection to Möbius Inversion

The lattice of set partitions of V refines Whitney's formula. For each partition π of V, let G/π be the graph obtained by contracting each block to a single vertex. The chromatic polynomial can be expressed via Möbius inversion on the partition lattice:

P(G, k) = Σ_π μ(0̂, π) · k^|π|

where the sum is over all partitions π such that each block of π is connected in G, |π| denotes the number of blocks, and μ is the Möbius function of the partition lattice. This deep connection to algebraic combinatorics underpins the theory of the Tutte polynomial — a two-variable generalization that encodes the chromatic polynomial, the flow polynomial, and the reliability polynomial simultaneously.

C++ Implementation

Approach 1: Deletion-Contraction with Memoization

We represent graphs as adjacency bitmasks. Each graph state is hashed for memoization. This approach works well for sparse graphs with up to ~20 vertices.

#include <bits/stdc++.h>
using namespace std;

// Graph represented as upper-triangular adjacency bitmask
// For n vertices, edge (i,j) with i < j stored in bit (i*n + j)
struct Graph {
    int n;
    vector<int> adj; // adj[v] = bitmask of neighbors

    bool operator==(const Graph& o) const {
        return n == o.n && adj == o.adj;
    }
};

struct GraphHash {
    size_t operator()(const Graph& g) const {
        size_t h = hash<int>()(g.n);
        for (int x : g.adj)
            h ^= hash<int>()(x) + 0x9e3779b9 + (h << 6) + (h >> 2);
        return h;
    }
};

unordered_map<Graph, vector<long long>, GraphHash> memo;

// Returns chromatic polynomial as coefficient vector:
// result[i] = coefficient of k^i
vector<long long> chromatic_poly(Graph g) {
    if (memo.count(g)) return memo[g];

    // Base case: no edges → k^n
    bool has_edge = false;
    int u = -1, v = -1;
    for (int i = 0; i < g.n && !has_edge; i++)
        for (int j = i + 1; j < g.n && !has_edge; j++)
            if (g.adj[i] >> j & 1) { has_edge = true; u = i; v = j; }

    if (!has_edge) {
        // P(G,k) = k^n
        vector<long long> res(g.n + 1, 0);
        res[g.n] = 1;
        return memo[g] = res;
    }

    // Deletion: remove edge (u, v)
    Graph del = g;
    del.adj[u] &= ~(1 << v);
    del.adj[v] &= ~(1 << u);
    auto p_del = chromatic_poly(del);

    // Contraction: merge v into u, remove vertex v
    Graph con;
    con.n = g.n - 1;
    con.adj.assign(con.n, 0);
    // Merge neighborhoods: u inherits v's neighbors
    int merged_adj = (g.adj[u] | g.adj[v]) & ~(1 << u) & ~(1 << v);

    auto remap = [&](int x) -> int {
        return x < v ? x : x - 1;
    };

    for (int i = 0; i < g.n; i++) {
        if (i == v) continue;
        int ni = remap(i);
        for (int j = i + 1; j < g.n; j++) {
            if (j == v) continue;
            int nj = remap(j);
            bool edge = (g.adj[i] >> j) & 1;
            // Also add edges from merged vertex
            if (i == u) edge |= (g.adj[v] >> j) & 1;
            if (j == u) edge |= (g.adj[v] >> i) & 1;
            if (edge) {
                con.adj[ni] |= 1 << nj;
                con.adj[nj] |= 1 << ni;
            }
        }
    }

    auto p_con = chromatic_poly(con);

    // P(G,k) = P(G-e,k) - P(G/e,k)
    int sz = max(p_del.size(), p_con.size());
    vector<long long> res(sz, 0);
    for (int i = 0; i < (int)p_del.size(); i++) res[i] += p_del[i];
    for (int i = 0; i < (int)p_con.size(); i++) res[i] -= p_con[i];

    return memo[g] = res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    Graph g;
    g.n = n;
    g.adj.assign(n, 0);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        g.adj[u] |= 1 << v;
        g.adj[v] |= 1 << u;
    }

    auto poly = chromatic_poly(g);

    // Print polynomial coefficients
    cout << "P(G, k) =";
    bool first = true;
    for (int i = (int)poly.size() - 1; i >= 0; i--) {
        if (poly[i] == 0) continue;
        if (!first && poly[i] > 0) cout << " +";
        cout << " " << poly[i] << "k^" << i;
        first = false;
    }
    cout << "\n";

    // Evaluate at k = 1, 2, 3, ...
    for (int k = 1; k <= n + 2; k++) {
        long long val = 0, pk = 1;
        for (int i = 0; i < (int)poly.size(); i++) {
            val += poly[i] * pk;
            pk *= k;
        }
        cout << "P(G, " << k << ") = " << val << "\n";
    }
}

Approach 2: Bitmask DP (Inclusion-Exclusion)

For small graphs (n ≤ 20), the fastest practical approach computes P(G, k) using Whitney's formula with subset-sum convolution. We iterate over all 2ⁿ subsets of vertices (equivalently, contractions) and use the inclusion-exclusion formula.

In practice, the cleaner formulation uses the independent-set polynomial. Here is a streamlined O(2ⁿ · n) implementation:

#include <bits/stdc++.h>
using namespace std;

// Count proper k-colorings of graph with n vertices (n ≤ 20)
// adj[v] = bitmask of neighbors of vertex v
long long count_colorings(int n, vector<int>& adj, int k) {
    // For each subset S, compute number of connected components
    // when we identify all vertices in each "color class"

    // Step 1: precompute for each subset, whether it is independent
    vector<bool> is_indep(1 << n, true);
    for (int mask = 1; mask < (1 << n); mask++) {
        int v = __builtin_ctz(mask); // lowest set bit
        int rest = mask & (mask - 1);
        // mask is independent iff rest is independent
        // AND v has no neighbors in rest
        is_indep[mask] = is_indep[rest] && ((adj[v] & rest) == 0);
    }

    // Step 2: count independent subsets of each subset
    // (this is the independent set polynomial evaluation)
    // g[mask] = number of independent subsets of mask
    vector<long long> g(1 << n, 0);
    g[0] = 1;
    for (int mask = 1; mask < (1 << n); mask++) {
        // iterate over submasks that are independent
        // Using Möbius / zeta transform approach for speed
        if (is_indep[mask]) g[mask] = 1;
    }

    // Actually, for counting colorings we use a different DP.
    // Let f[S] = number of ways to partition S into ≤ k independent sets.
    // Then P(G, k) = f[V].

    // Efficient approach: count the number of independent sets
    // for each vertex subset, then use subset convolution.

    // Simpler O(2^n * n) approach using inclusion-exclusion:
    // P(G, k) = sum over S ⊆ V of (-1)^{|V|-|S|} * (number of surjective
    //           k-colorings restricted to S)
    // But the cleanest is the direct formula:

    // P(G, k) = sum_{S ⊆ V} (-1)^{n-|S|} * q(S) * k^{|S|}
    // where q(S) checks a certain partition condition.

    // The standard bitmask approach:
    // Let I[mask] = 1 if mask is an independent set, 0 otherwise.
    // Compute h[mask] = number of independent subsets of mask
    //                  (sum of I[sub] over all sub ⊆ mask).
    // Then P(G, k) = sum_{mask ⊆ V} (-1)^{n - popcount(mask)} * h[mask]^k
    // Wait — that's not quite right either.

    // CORRECT formulation (Björklund et al., 2009):
    // P(G, k) = sum_{S ⊆ V} (-1)^{n-|S|} * p(S)^k
    // where p(S) = number of independent sets in G[S].
    // This is WRONG; the correct formula is:

    // Actually, the correct inclusion-exclusion formula is:
    // Number of proper k-colorings =
    //   sum_{S ⊆ V} (-1)^{|S|} * (k)^{c(V, E restricted to complement of S)}
    // where... this gets complicated.

    // Let's use the simplest correct approach:
    // Define: for subset S ⊆ V, let a(S) = 1 if S is independent, else 0.
    // Let  b[S] = sum_{T ⊆ S} a(T) = number of independent subsets of S.
    // Then: P(G, k) = sum_{S ⊆ V} (-1)^{n - |S|} * b(S) * (k choose |S|) * |S|! ???
    // No. Let me just implement the standard approach correctly.

    // STANDARD APPROACH: directly via inclusion-exclusion on color classes.
    // We want to count the number of onto-k-coloring (surjective) then scale.
    // Actually P(G,k) counts all proper colorings (not necessarily surjective).

    // Simplest correct O(2^n * n): use the formula
    //   P(G,k) = sum_{S ⊆ V} (-1)^{n-|S|} * k^{comp(S)}
    // where comp(S) = number of connected components of G[S].
    // Here G[S] is the induced subgraph on vertex set S.

    // Precompute number of connected components of G[S] for each S
    vector<int> comp(1 << n, 0);
    for (int mask = 1; mask < (1 << n); mask++) {
        // BFS/DFS to count components
        int visited = 0, c = 0;
        int tmp = mask;
        while (tmp & (~visited)) {
            int start = __builtin_ctz(tmp & (~visited));
            // BFS from start within mask
            int queue_mask = 1 << start;
            visited |= 1 << start;
            while (queue_mask) {
                int v = __builtin_ctz(queue_mask);
                queue_mask &= queue_mask - 1;
                int neighbors = adj[v] & mask & (~visited);
                visited |= neighbors;
                queue_mask |= neighbors;
            }
            c++;
        }
        comp[mask] = c;
    }

    // P(G, k) = sum_{S ⊆ V} (-1)^{n-|S|} * k^{comp(S)}
    long long result = 0;
    int full = (1 << n) - 1;
    for (int mask = 0; mask <= full; mask++) {
        int sz = __builtin_popcount(mask);
        long long sign = ((n - sz) % 2 == 0) ? 1 : -1;
        long long val = 1;
        int c = (mask == 0) ? 0 : comp[mask];
        for (int i = 0; i < c; i++) val *= k;
        result += sign * val;
    }
    return result;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<int> adj(n, 0);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        adj[u] |= 1 << v;
        adj[v] |= 1 << u;
    }

    // Evaluate P(G, k) for k = 0, 1, ..., n
    // From n+1 evaluations we can recover the polynomial via interpolation
    cout << "Evaluations:\n";
    for (int k = 0; k <= n; k++) {
        cout << "P(G, " << k << ") = "
             << count_colorings(n, adj, k) << "\n";
    }
}

Chromatic Number

The chromatic number χ(G) is the smallest number of colors needed for a proper coloring of G. Equivalently:

χ(G) = min { k ∈ ℤ⁺ : P(G, k) > 0 }

Upper Bounds

Greedy bound: A greedy coloring using any vertex ordering produces a coloring with at most Δ(G) + 1 colors, where Δ(G) is the maximum degree.

This is a tighter bound than the greedy one for most graphs. For example, a 4-regular planar graph has Δ = 4, and Brooks' theorem guarantees χ ≤ 4 — consistent with the Four Color Theorem.

Lower Bounds

• Clique number: χ(G) ≥ ω(G), since vertices in a clique all need distinct colors.
• Odd cycle: If G contains an odd cycle, χ(G) ≥ 3.
• Fractional chromatic number: χ(G) ≥ χ_f(G) ≥ n / α(G), where α(G) is the independence number.

Exact Computation for Contests

For small n (≤ 20), we can find χ(G) exactly using the bitmask DP from above: simply evaluate P(G, k) for k = 1, 2, 3, … until P(G, k) > 0. A faster approach uses inclusion-exclusion directly:

#include <bits/stdc++.h>
using namespace std;

// Find chromatic number of graph with n ≤ 20 vertices
int chromatic_number(int n, vector<int>& adj) {
    // is_indep[mask] = 1 if induced subgraph on mask is independent set
    vector<int> is_indep(1 << n, 1);
    for (int mask = 1; mask < (1 << n); mask++) {
        int v = __builtin_ctz(mask);
        int rest = mask ^ (1 << v);
        is_indep[mask] = is_indep[rest] && ((adj[v] & rest) == 0);
    }

    // s[mask] = number of independent subsets of mask
    // Computed via subset-sum (zeta transform over subsets)
    vector<long long> s(1 << n, 0);
    for (int mask = 0; mask < (1 << n); mask++) {
        s[mask] = is_indep[mask];
    }
    // Subset sum transform: s[mask] = sum_{sub ⊆ mask} is_indep[sub]
    for (int i = 0; i < n; i++) {
        for (int mask = 0; mask < (1 << n); mask++) {
            if (mask & (1 << i)) {
                s[mask] += s[mask ^ (1 << i)];
            }
        }
    }

    // Inclusion-exclusion: check if k colors suffice
    // f(k) = sum_{S ⊆ V} (-1)^{n-|S|} * s(S)^k
    // If f(k) > 0, then k colors suffice.
    int full = (1 << n) - 1;
    for (int k = 1; k <= n; k++) {
        long long total = 0;
        for (int mask = 0; mask <= full; mask++) {
            int sz = __builtin_popcount(mask);
            long long sign = ((n - sz) % 2 == 0) ? 1 : -1;
            // s[mask]^k — careful of overflow for large k
            long long val = 1;
            for (int i = 0; i < k; i++) val *= s[mask];
            total += sign * val;
        }
        if (total > 0) return k;
    }
    return n; // fallback: n colors always suffice
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<int> adj(n, 0);
    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v; u--; v--;
        adj[u] |= 1 << v;
        adj[v] |= 1 << u;
    }
    cout << "Chromatic number: " << chromatic_number(n, adj) << "\n";
}

CP Applications

Chromatic polynomials and graph coloring appear across competitive programming in several guises:

1. Direct Graph Coloring

The most obvious application: "How many ways to color a graph with k colors?" If the graph is a tree, cycle, or has other known structure, use the closed-form formulas. Otherwise, apply bitmask DP for small n.

2. Scheduling and Conflict Graphs

Many scheduling problems reduce to graph coloring: tasks that conflict share an edge, and colors represent time slots. The chromatic number gives the minimum number of time slots. Even when you can't compute χ(G) exactly, the greedy bound Δ(G) + 1 gives a feasible schedule.

3. Counting Colorings Modulo a Prime

A frequent contest pattern: "Count the number of proper k-colorings of G modulo 10⁹+7." Since P(G, k) is a polynomial, you can:

1. Compute P(G, k) mod p for k = 0, 1, …, n (n+1 evaluations).
2. Use Lagrange interpolation to recover the polynomial mod p.
3. Evaluate at any desired k in O(n) time.

This avoids computing the polynomial symbolically and works entirely in modular arithmetic.

4. Inclusion-Exclusion on Graphs

The chromatic polynomial is a canonical example of inclusion-exclusion on graph structure. The same technique generalizes to:

• Counting independent sets of a given size.
• Counting Hamiltonian paths (via similar bitmask DP, though the formula differs).
• Permanent of a 0/1 matrix (Ryser's formula uses the same inclusion-exclusion pattern).

5. Bipartite Checking as 2-Colorability

The simplest chromatic-polynomial question: P(G, 2) > 0 iff G is bipartite. For bipartite graphs, P(G, 2) = 2^c where c is the number of connected components (each component can be 2-colored in exactly 2 ways up to the first vertex's choice). This connects to the standard BFS/DFS bipartiteness check.

6. Map Coloring and Planar Graphs

The Four Color Theorem states χ(G) ≤ 4 for all planar graphs. In contest problems involving maps or planar graphs, this guarantees a small chromatic number. The Five Color Theorem (easier to prove and implement) gives a constructive O(n) algorithm.

Summary

Next up: In Part 7 — Ramsey Theory, we explore the guaranteed existence of monochromatic structures in colored graphs — a deep connection between combinatorics and graph coloring that produces some of the hardest open problems in mathematics.