Two-Colorable

Tags

Two-Colorable

Category

Graphs

Difficulty

Medium

Problem Statement

Given an undirected graph represented as an adjacency list, determine if the graph is two-colorable (bipartite). A graph is two-colorable if every node can be assigned one of two colors such that no two adjacent nodes share the same color.

Intuition

A graph is bipartite if and only if it contains no odd-length cycles. To check this, we perform a BFS (or DFS) and try to assign alternating colors to nodes level by level. If we ever find two adjacent nodes with the same color, the graph is not bipartite.

This is equivalent to checking whether the graph can be partitioned into two independent sets.

Approach

  1. Initialize a color array with all values set to "uncolored" (e.g., -1).
  2. For each uncolored node (to handle disconnected components): a. Assign it a color (e.g., 0) and add it to a BFS queue. b. Process the queue:
    • For each neighbor of the current node:
      • If uncolored, assign the opposite color and enqueue it.
      • If already colored with the same color as the current node, return false.
  3. If all nodes are successfully colored, return true.

Pseudocode

function twoColorable(edges):
    n = length(edges)
    colors = array of n, all -1 (uncolored)

    for node from 0 to n - 1:
        if colors[node] != -1:
            continue
        colors[node] = 0
        queue = [node]
        while queue is not empty:
            current = queue.dequeue()
            for neighbor in edges[current]:
                if colors[neighbor] == -1:
                    colors[neighbor] = 1 - colors[current]
                    queue.enqueue(neighbor)
                else if colors[neighbor] == colors[current]:
                    return false

    return true

Time & Space Complexity

  • Time: O(V + E), where V is the number of vertices and E is the number of edges. Each node and edge is processed once.
  • Space: O(V) for the color array and BFS queue.

Key Insights

  • A graph is bipartite if and only if it has no odd-length cycles. BFS/DFS coloring detects this efficiently.
  • Trees are always bipartite (they have no cycles at all).
  • Self-loops make a graph immediately non-bipartite (a node cannot be two colors at once).
  • Disconnected graphs require checking each connected component separately.
  • Bipartite graphs have many practical applications: matching problems, scheduling, and conflict-free assignments.

Edge Cases

  • Graph with no edges: always two-colorable (any coloring works).
  • Single node with a self-loop: not two-colorable.
  • Complete graph (K_n): two-colorable only if n <= 2.
  • Disconnected graph: each component must independently be two-colorable.
  • Graph that is a single cycle: two-colorable if the cycle length is even, not if odd.
  • Tree: always two-colorable.

Linked mentions