Bipartite Testing & k-Colorability Backtracking

A Short History of Graph Coloring

Coloring began as a structural question—how many labels are needed so adjacent regions or vertices differ—and later became a central language for algorithmic complexity and constraint solving.

The resulting contrast is unusually sharp: 2-colorability has a linear-time structural test, while every fixed $k \geq 3$ gives an NP-complete decision problem on general graphs.

Coloring as a Constraint Problem

A proper $k$-coloring is a function $c:V\to\{0,\ldots,k-1\}$ satisfying $c(u)\ne c(v)$ for every edge $(u,v)$. Each color class is therefore an independent set. The smallest feasible $k$ is the chromatic number $\chi(G)$.

2-Colorability: BFS/DFS Bipartiteness Test

Two colors are special because an edge leaves no choice: once $c(u)$ is known, every neighbor $v$ must receive $1-c(u)$. A traversal can therefore propagate forced colors instead of guessing them.

Turning “No” into an Odd-Cycle Certificate

A boolean answer is useful; a witness is better. Keep a parent pointer for every discovered vertex. When a conflict edge $(u,v)$ joins equal colors, walk both parent chains to their lowest common ancestor $a$. Concatenate the path $u\leadsto a$, the reversed path $a\leadsto v$, and the conflict edge $(v,u)$.

Because $u$ and $v$ have the same parity, their tree path has even length. Closing it with one more edge makes the cycle odd. The Python implementation below returns this closed vertex sequence so callers can inspect, test, or display the exact obstruction.

k-Colorability: Backtracking Search

For $k\geq3$, an edge no longer determines one forced choice: after seeing a red neighbor, a vertex may still choose blue, green, or another available color. The problem becomes a constraint-satisfaction search:

Search Heuristics & Propagation

Heuristics do not change which instances are colorable; they change how quickly the search discovers a witness or contradiction. The exact Python solver combines three inexpensive ideas:

• DSATUR ordering: choose the uncolored vertex adjacent to the largest number of distinct colors. Break ties by degree, then vertex index for deterministic output.
• Forward checking: after each assignment, reject immediately if any uncolored vertex has lost every color.
• Color symmetry breaking: when a search component has no colored neighbor, try color 0 first. Renaming colors produces equivalent solutions, so symmetric root branches add no information.

Worked Example

Even cycle: propagation succeeds

For the square 0-1-2-3-0, start at vertex 0 with teal. BFS forces vertices 1 and 3 to navy, then vertex 2 to teal. The closing edge $(2,3)$ joins teal to navy, so no conflict appears.

$K_4$: three colors fail

Vertices 0, 1, and 2 form a triangle, so they must use three distinct colors. Vertex 3 is adjacent to all three; each candidate color conflicts with one neighbor. Every branch is equivalent up to renaming the three colors, so backtracking eventually proves that $K_4$ is not 3-colorable. A fourth color immediately supplies a witness.

Complexity Analysis

The two algorithms differ because propagation is complete for two colors but incomplete for three or more. Let $n=|V|$ and $m=|E|$.

The boundary cases are worth handling explicitly: $k=1$ succeeds only for an edgeless graph; $k=2$ should use the linear bipartite test; and any loop-free graph with $k\geq n$ is trivially colorable. For every fixed $k\geq3$, the decision problem is NP-complete on general graphs.

Implementation

The Python version returns both kinds of bipartite certificate and uses DSATUR plus forward checking for exact $k$-color search. The C++ and Java tabs keep the same graph model and demonstrate compact decision versions. All snippets assume an undirected adjacency list; each undirected edge must appear in both endpoint lists.

from collections import deque

def validate_undirected_graph(adj):
    """Return sorted, duplicate-free neighbor lists or raise ValueError."""
    n = len(adj)
    neighbors = []
    for row in adj:
        clean = set()
        for v in row:
            if not isinstance(v, int) or not 0 <= v < n:
                raise ValueError("neighbor index out of range")
            clean.add(v)
        neighbors.append(clean)

    for u, row in enumerate(neighbors):
        for v in row:
            if u not in neighbors[v]:
                raise ValueError("adjacency list must be symmetric")
    return [sorted(row) for row in neighbors]


def odd_cycle_from_conflict(u, v, parent):
    """Close the two parent paths with conflict edge (v, u)."""
    if u == v:                       # a self-loop
        return [u, u]

    path_u = []
    x = u
    while x != -1:
        path_u.append(x)
        x = parent[x]
    position = {x: i for i, x in enumerate(path_u)}

    path_v = []
    y = v
    while y not in position:
        path_v.append(y)
        y = parent[y]

    # u ... LCA ... v, followed implicitly by conflict edge v -> u
    return path_u[:position[y] + 1] + list(reversed(path_v)) + [u]


def is_bipartite(adj):
    """Return (is_bipartite, colors, odd_cycle_or_none)."""
    neighbors = validate_undirected_graph(adj)
    n = len(neighbors)
    color = [-1] * n
    parent = [-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 neighbors[u]:
                if color[v] == -1:
                    color[v] = 1 - color[u]
                    parent[v] = u
                    q.append(v)
                elif color[v] == color[u]:
                    cycle = odd_cycle_from_conflict(u, v, parent)
                    return False, color, cycle

    return True, color, None


def k_colorable(adj, k):
    """Return an exact k-coloring, or None if none exists."""
    if not isinstance(k, int) or k < 1:
        raise ValueError("k must be a positive integer")
    neighbors = validate_undirected_graph(adj)
    n = len(neighbors)

    if any(v in neighbors[v] for v in range(n)):
        return None
    if n == 0:
        return []
    if k == 2:
        ok, color, _ = is_bipartite(neighbors)
        return color if ok else None
    if k >= n:
        return list(range(n))

    colors = [-1] * n

    def used_colors(v):
        return {colors[u] for u in neighbors[v] if colors[u] != -1}

    def choose_vertex():
        uncolored = (v for v in range(n) if colors[v] == -1)
        return max(uncolored,
                   key=lambda v: (len(used_colors(v)), len(neighbors[v]), -v))

    def every_domain_nonempty():
        return all(colors[v] != -1 or len(used_colors(v)) < k
                   for v in range(n))

    def backtrack():
        if all(c != -1 for c in colors):
            return True

        v = choose_vertex()
        blocked = used_colors(v)
        candidates = [c for c in range(k) if c not in blocked]
        if not blocked:               # equivalent branches under color renaming
            candidates = [0]

        for c in candidates:
            colors[v] = c
            if every_domain_nonempty() and backtrack():
                return True
            colors[v] = -1
        return False

    return colors if backtrack() else None

# A 4-cycle: returns two color classes
square = [[] for _ in range(4)]
for u, v in [(0,1),(1,2),(2,3),(3,0)]:
    square[u].append(v); square[v].append(u)
print(is_bipartite(square))

# K4: no 3-coloring, but a 4-coloring exists
k4 = [[1,2,3],[0,2,3],[0,1,3],[0,1,2]]
print("3-colorable K4:", k_colorable(k4, 3))
print("4-colorable K4:", k_colorable(k4, 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 (u == v || 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 (u == v || 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

The mathematical model is useful whenever pairwise incompatibilities must be separated. The graph must be defined carefully: vertices represent choices or resources, and an edge must mean “these two cannot share a group.”

Exercises

Limitations

• Decision is not optimization: a successful $k$-coloring proves $chi(G)\leq k$, not that $k$ is minimal.
• Model assumptions matter: these routines expect an undirected adjacency list. A self-loop makes every proper coloring impossible; parallel entries do not change colorability.
• Recursion can be deep: exact search may reach depth $n$ and can require an iterative stack or a larger recursion limit in production environments.
• Heuristics are instance-dependent: the best ordering can vary. Dense and sparse graphs may favor different tie-breakers, bounds, or decompositions.