Algorithm Deep Dive: Bipartite Testing & k-Colorability Backtracking

A Bit of History

Bipartiteness testing traces back to Dénes Kőnig's foundational 1936 graph theory textbook, which formally characterized bipartite graphs as exactly those containing no odd-length cycle — a theorem that translates directly into a linear-time algorithmic test via BFS or DFS 2-coloring. The general $k$-colorability problem's difficulty was cemented in 1972 by Richard Karp, who proved 3-Colorability NP-complete in the same paper that established Hamiltonian Cycle's hardness — meaning the jump from "2 colors" to "3 colors" isn't a small step up in difficulty, but a leap across one of computer science's most fundamental complexity boundaries.

2-Colorability: BFS/DFS Bipartiteness Test

A graph is 2-colorable (equivalently, bipartite) if and only if it contains no odd-length cycle. This can be tested in a single linear-time traversal:

Assign the starting vertex of each connected component color 0.
Run BFS or DFS; whenever you traverse an edge $(u, v)$, assign $v$ the opposite color from $u$.
If you ever encounter an edge $(u, v)$ where both endpoints are already colored the same, the graph is not bipartite — reject immediately.
If the traversal completes without conflict across every component, the graph is bipartite, and the 2-coloring is a valid partition into two independent sets.

Why This Works

BFS/DFS naturally alternates colors by distance parity from the root — vertices at even distance get one color, odd distance the other. A same-color conflict on edge $(u,v)$ means $u$ and $v$ are at the same parity distance from the root, which (combined with the tree-path back to their common ancestor) forms an odd cycle — exactly the forbidden structure Kőnig's theorem rules out.

k-Colorability: Backtracking Search

For $k \geq 3$, no known polynomial-time test exists. The standard approach is backtracking over vertex-color assignments:

Process vertices in a fixed order (e.g., vertex index, or a heuristic order like most-constrained-first).
For each vertex, try each of the $k$ colors in turn, but only if no already-colored neighbor already has that color.
If a color choice succeeds, recurse to the next vertex. If all $k$ colors fail for the current vertex, backtrack and try the previous vertex's next color option.
If every vertex gets successfully colored, a valid $k$-coloring exists; if backtracking exhausts all options at the root, no valid $k$-coloring exists.

Worked Example

2-Colorability: square graph 0-1-2-3-0 (a 4-cycle, even length). BFS from 0: color(0)=A, color(1)=B, color(2)=A, color(3)=B. Check closing edge 3-0: colors B and A differ — no conflict, graph is bipartite.

3-Colorability: triangle graph 0-1-2-0 plus an isolated vertex 3 connected to all three (a "wheel" $W_3$, which is $K_4$). Try color(0)=1: color(1) must differ, try 2. color(2) must differ from both 0 and 1, try 3. color(3) must differ from 0, 1, AND 2 — but only 3 colors exist and all three are already used by its neighbors! Backtrack exhausted — $K_4$ requires 4 colors, confirming it is NOT 3-colorable.

Complexity Analysis

Problem	Time Complexity	Complexity Class
2-Colorability (Bipartiteness)	$O(V + E)$	P (polynomial)
$k$-Colorability, $k \geq 3$	$O(k^V)$ worst case	NP-complete

Implementation

from collections import deque

def is_bipartite(n, adj):
    """Linear-time 2-colorability test via BFS."""
    color = [-1] * n

    for start in range(n):
        if color[start] != -1:
            continue
        color[start] = 0
        q = deque([start])

        while q:
            u = q.popleft()
            for v in adj[u]:
                if color[v] == -1:
                    color[v] = 1 - color[u]
                    q.append(v)
                elif color[v] == color[u]:
                    return False, None  # same-color conflict -> odd cycle

    return True, color

def k_colorable(n, adj, k):
    """Backtracking search for a valid k-coloring."""
    colors = [-1] * n

    def is_safe(v, c):
        return all(colors[u] != c for u in adj[v])

    def backtrack(v):
        if v == n:
            return True
        for c in range(k):
            if is_safe(v, c):
                colors[v] = c
                if backtrack(v + 1):
                    return True
                colors[v] = -1
        return False

    if backtrack(0):
        return colors
    return None

# Test 2-colorability on a 4-cycle
n = 4
adj = [[] for _ in range(n)]
for u, v in [(0,1),(1,2),(2,3),(3,0)]:
    adj[u].append(v); adj[v].append(u)
print("Is bipartite:", is_bipartite(n, adj))

# Test 3-colorability on K4 (should fail)
n2 = 4
adj2 = [[1,2,3],[0,2,3],[0,1,3],[0,1,2]]
print("3-colorable K4:", k_colorable(n2, adj2, 3))
print("4-colorable K4:", k_colorable(n2, adj2, 4))

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

bool isBipartite(int n, vector<vector<int>>& adj) {
    vector<int> color(n, -1);

    for (int start = 0; start < n; start++) {
        if (color[start] != -1) continue;
        color[start] = 0;
        queue<int> q; q.push(start);

        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : adj[u]) {
                if (color[v] == -1) {
                    color[v] = 1 - color[u];
                    q.push(v);
                } else if (color[v] == color[u]) {
                    return false;
                }
            }
        }
    }
    return true;
}

bool isSafe(int v, int c, vector<vector<int>>& adj, vector<int>& colors) {
    for (int u : adj[v]) if (colors[u] == c) return false;
    return true;
}

bool backtrackColor(int v, int n, int k, vector<vector<int>>& adj, vector<int>& colors) {
    if (v == n) return true;
    for (int c = 0; c < k; c++) {
        if (isSafe(v, c, adj, colors)) {
            colors[v] = c;
            if (backtrackColor(v + 1, n, k, adj, colors)) return true;
            colors[v] = -1;
        }
    }
    return false;
}

int main() {
    int n = 4;
    vector<vector<int>> adj(n);
    for (auto& e : vector<pair<int,int>>{{0,1},{1,2},{2,3},{3,0}}) {
        adj[e.first].push_back(e.second);
        adj[e.second].push_back(e.first);
    }
    cout << "Is bipartite: " << isBipartite(n, adj) << endl;

    vector<vector<int>> k4 = {{1,2,3},{0,2,3},{0,1,3},{0,1,2}};
    vector<int> colors(4, -1);
    cout << "3-colorable K4: " << backtrackColor(0, 4, 3, k4, colors) << endl;
    return 0;
}

import java.util.*;

public class BipartiteKColoring {
    public static boolean isBipartite(int n, List<List<Integer>> adj) {
        int[] color = new int[n];
        Arrays.fill(color, -1);

        for (int start = 0; start < n; start++) {
            if (color[start] != -1) continue;
            color[start] = 0;
            Deque<Integer> q = new ArrayDeque<>();
            q.add(start);

            while (!q.isEmpty()) {
                int u = q.poll();
                for (int v : adj.get(u)) {
                    if (color[v] == -1) {
                        color[v] = 1 - color[u];
                        q.add(v);
                    } else if (color[v] == color[u]) {
                        return false;
                    }
                }
            }
        }
        return true;
    }

    static boolean isSafe(int v, int c, List<List<Integer>> adj, int[] colors) {
        for (int u : adj.get(v)) if (colors[u] == c) return false;
        return true;
    }

    static boolean backtrack(int v, int n, int k, List<List<Integer>> adj, int[] colors) {
        if (v == n) return true;
        for (int c = 0; c < k; c++) {
            if (isSafe(v, c, adj, colors)) {
                colors[v] = c;
                if (backtrack(v + 1, n, k, adj, colors)) return true;
                colors[v] = -1;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int n = 4;
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        int[][] edges = {{0,1},{1,2},{2,3},{3,0}};
        for (int[] e : edges) {
            adj.get(e[0]).add(e[1]);
            adj.get(e[1]).add(e[0]);
        }
        System.out.println("Is bipartite: " + isBipartite(n, adj));

        List<List<Integer>> k4 = new ArrayList<>();
        int[][] k4Edges = {{1,2,3},{0,2,3},{0,1,3},{0,1,2}};
        for (int[] neighbors : k4Edges) {
            List<Integer> list = new ArrayList<>();
            for (int x : neighbors) list.add(x);
            k4.add(list);
        }
        int[] colors = new int[4];
        Arrays.fill(colors, -1);
        System.out.println("3-colorable K4: " + backtrack(0, 4, 3, k4, colors));
    }
}

Real-World Applications

Case Study

Bipartite Matching Preprocessing & SAT Solver Reductions

Bipartiteness testing is a standard preprocessing step before applying bipartite-specific algorithms like Hopcroft-Karp or Hungarian Algorithm — verifying the graph actually qualifies. 3-Colorability's NP-completeness makes it a canonical target for reduction proofs; many SAT solvers and constraint satisfaction engines are benchmarked by translating 3-coloring instances into Boolean satisfiability problems and back.

Matching AlgorithmsComplexity Theory

Exercises

Prove Kőnig's theorem in one direction: show that any graph containing an odd cycle cannot be 2-colored.
Determine the chromatic number of the Petersen graph via backtracking and compare it to its known value (3).
Add most-constrained-vertex ordering (color the highest-degree vertex first) to the backtracking search and measure the practical speedup.
Challenge: Implement a SAT-based 3-colorability solver by encoding "vertex $v$ has color $c$" as boolean variables and constraints, then compare its performance to direct backtracking.

Limitations

The P vs. NP Cliff at k=3

There is no smooth complexity gradient here — 2-colorability is solvable in linear time, but 3-colorability (and every $k \geq 3$) is NP-complete, with no known sub-exponential algorithm. Backtracking with good heuristics (DSatur-style ordering, constraint propagation) helps in practice but offers no worst-case guarantee.

Cookie Consent

Bipartite Testing & k-Colorability Backtracking

Contents

A Bit of History

2-Colorability: BFS/DFS Bipartiteness Test

Why This Works

k-Colorability: Backtracking Search

Worked Example

Complexity Analysis

Implementation

Real-World Applications

Bipartite Matching Preprocessing & SAT Solver Reductions

Exercises

Limitations

The P vs. NP Cliff at k=3

Cookie Consent

Bipartite Testing & k-Colorability Backtracking

Contents

A Bit of History

2-Colorability: BFS/DFS Bipartiteness Test

Why This Works

k-Colorability: Backtracking Search

Worked Example

Complexity Analysis

Implementation

Real-World Applications

Bipartite Matching Preprocessing & SAT Solver Reductions

Exercises

Limitations

The P vs. NP Cliff at k=3

Related Deep Dives

Graph Theory Series

Graph Coloring Heuristics

Part 13: Graph Coloring