Graph Coloring and Bipartite Checking

Terminology

Term	Definition
Graph coloring	Assigning labels (colors) to graph vertices such that no two adjacent vertices share the same color.
$k$-coloring	A valid coloring using at most $k$ colors. A graph is $k$-colorable if such a coloring exists.
Chromatic number $\chi(G)$	The minimum number of colors needed to properly color graph $G$. Finding $\chi(G)$ is NP-hard in general.
Bipartite graph	A graph whose vertices can be divided into two disjoint sets such that every edge connects a vertex in one set to a vertex in the other. Equivalently, a graph that is 2-colorable.

2-coloring Assigning one of two colors to each vertex. A graph is 2-colorable if and only if it is bipartite (contains no odd-length cycles). Odd cycle A cycle with an odd number of edges. A graph is bipartite if and only if it contains no odd cycles. BFS coloring Starting from an uncolored node, assign it color 0, then assign alternating colors to neighbors layer by layer. If a conflict is found, the graph is not bipartite. Possible bipartition A LeetCode problem: given a list of "dislike" pairs, determine if people can be split into two groups such that no two people in the same group dislike each other. This is bipartite checking on the dislike graph.

What & Why

Graph coloring asks: can you assign colors to vertices so that no two adjacent vertices share a color? The simplest and most practical case is 2-coloring, which is equivalent to checking whether a graph is bipartite.

Bipartite checking appears in many disguised forms: "can we split people into two teams with no conflicts?", "is this graph a valid matching candidate?", "can we 2-partition this set?" All reduce to: does the graph contain an odd cycle?

The algorithm is straightforward: BFS (or DFS) from each unvisited node, assigning alternating colors. If you ever try to color a node that already has the wrong color, the graph is not bipartite.

General k-coloring for k \geq 3 is NP-complete, but 2-coloring runs in O(V + E), making it one of the few coloring problems solvable in polynomial time.

How It Works

BFS 2-Coloring

Start from any uncolored node, color it 0. Put it in a queue. For each node dequeued, color all uncolored neighbors with the opposite color. If a neighbor is already colored with the same color, the graph is not bipartite.

The graph on the left is bipartite: vertices alternate between blue and orange with no conflicts. The triangle on the right has an odd cycle (length 3), so 2-coloring is impossible.

Complexity Analysis

Problem	Time	Space
Bipartite check (2-coloring)	$O(V + E)$	$O(V)$
Possible bipartition	$O(V + E)$	$O(V + E)$
3-coloring (decision)	NP-complete	-
Chromatic number	NP-hard	-

BFS/DFS visits every vertex once and every edge once. The color array uses $O(V)$ space:

The key theorem: a graph is bipartite if and only if it contains no odd-length cycle. BFS detects this by finding a same-color conflict.

Implementation

Bipartite Check via BFS

ALGORITHM IsBipartite(graph, V)
  INPUT: adjacency list graph with V vertices
  OUTPUT: TRUE if graph is bipartite

  color = array of size V, filled with -1 (uncolored)

  FOR node = 0 TO V - 1 DO
    IF color[node] != -1 THEN CONTINUE

    // BFS from this unvisited node
    queue = empty queue
    queue.enqueue(node)
    color[node] = 0

    WHILE queue is not empty DO
      u = queue.dequeue()

      FOR EACH v IN graph[u] DO
        IF color[v] = -1 THEN
          color[v] = 1 - color[u]    // opposite color
          queue.enqueue(v)
        ELSE IF color[v] = color[u] THEN
          RETURN FALSE               // conflict: not bipartite
        END IF
      END FOR
    END WHILE
  END FOR

  RETURN TRUE
END

Bipartite Check via DFS

ALGORITHM IsBipartiteDFS(graph, V)
  color = array of size V, filled with -1

  FUNCTION DFS(node, c)
    color[node] = c

    FOR EACH neighbor IN graph[node] DO
      IF color[neighbor] = -1 THEN
        IF NOT DFS(neighbor, 1 - c) THEN
          RETURN FALSE
        END IF
      ELSE IF color[neighbor] = c THEN
        RETURN FALSE
      END IF
    END FOR

    RETURN TRUE
  END FUNCTION

  FOR node = 0 TO V - 1 DO
    IF color[node] = -1 THEN
      IF NOT DFS(node, 0) THEN
        RETURN FALSE
      END IF
    END IF
  END FOR

  RETURN TRUE
END

Possible Bipartition

ALGORITHM PossibleBipartition(n, dislikes)
  INPUT: n people, list of dislike pairs
  OUTPUT: TRUE if people can be split into two groups with no intra-group dislikes

  // Build adjacency list from dislikes
  graph = adjacency list of size n + 1

  FOR EACH (a, b) IN dislikes DO
    graph[a].append(b)
    graph[b].append(a)
  END FOR

  // Run bipartite check
  RETURN IsBipartite(graph, n + 1)
END

Real-World Applications

• Job scheduling: assigning tasks to two machines such that conflicting tasks run on different machines is a bipartite check on the conflict graph.
• Map coloring: the four color theorem guarantees any planar map can be colored with 4 colors. Graph coloring algorithms automate this for cartography.
• Register allocation: compilers model variable lifetimes as a graph and use graph coloring to assign CPU registers, minimizing spills to memory.
• Exam scheduling: students taking multiple exams create conflicts. Graph coloring assigns time slots so no student has two exams at once.
• Bipartite matching: matching problems (job assignments, stable marriage) require the underlying graph to be bipartite. Checking bipartiteness is the first step.

Key Takeaways

• A graph is bipartite if and only if it is 2-colorable, which is equivalent to having no odd-length cycles
• BFS or DFS with alternating colors checks bipartiteness in $O(V + E)$: assign color 0 to the start, color 1 to its neighbors, and detect conflicts
• "Possible bipartition" and "is graph bipartite" are the same problem: build the conflict graph and 2-color it
• General $k$-coloring for $k \geq 3$ is NP-complete, so there is no known polynomial algorithm. Greedy heuristics are used in practice
• The chromatic number $\chi(G)$ is the minimum colors needed. For bipartite graphs $\chi = 2$, for odd cycles $\chi = 3$, and the four color theorem gives $\chi \leq 4$ for planar graphs