L16. M-Coloring Problem | Backtracking

Main ideas / lesson

• The video explains the M-Coloring Problem on an undirected graph using a backtracking (recursive search) approach.
• Given:
  • An undirected graph (G)
  • An integer m (maximum number of colors allowed)
• Goal:
  • Determine whether the graph’s vertices can be colored using at most m colors such that no two adjacent vertices share the same color.
• Output:
  • Return true/1 if possible
  • Return false/0 if impossible
• Key conceptual points about the approach:
  • Try assigning colors recursively to vertices in some order (0, 1, 2, …).
  • For each vertex, try colors from 1 to m.
  • Use a safety check (“is it safe to color this vertex with color c?”) that ensures no neighbor already has color c.
  • If a choice leads to failure, backtrack by un-assigning the color and trying the next color.
  • Early exit: once a valid coloring is found, immediately return true without trying remaining colors.

Methodology / instructions (backtracking algorithm)

Define data structures

• Maintain a color array: color[v] stores the assigned color for vertex v (initially unset, often treated as 0).
• Use a graph representation that supports listing/checking adjacent neighbors.

Recursive function idea (try to color vertex by vertex)

• Input parameters:
  • node (current vertex index)
  • m (max colors)
  • n (number of vertices / also implied by graph size)
  • graph adjacency structure
  • color[] array
• Base case:
  • If node == n (i.e., all vertices have been successfully colored), return true.
• Recursive step:
  • For each color c from 1 to m:
    • Check whether assigning c to node is valid using isSafe(node, c)
    • If safe:
      • assign color[node] = c
      • recursively call the function for node + 1
      • if recursion returns true:
        • return true immediately (no need to try other colors)
      • otherwise:
        • backtrack by undoing the assignment via color[node] = 0 (or unset)
  • After trying all colors from 1..m and none work, return false.

Safety check function (isSafe)

• Input:
  • node (vertex being colored)
  • c (candidate color)
• For every adjacent neighbor k of node:
  • If color[k] == c, then coloring violates the constraint:
    • return false
• If no adjacent neighbor has color c:
  • return true

Examples discussed (conceptual walkthrough)

Example where coloring is possible

• Uses m = 3 on the depicted graph.
• Demonstrates trying colors sequentially and finding a full assignment that satisfies adjacency constraints.
• Highlights early return: once a valid assignment is reached, recursion unwinds returning true.

Example where coloring is not possible

• Same graph but m = 2.
• Shows recursion exploring options:
  • Eventually all color assignments fail,
  • returns false,
  • and backtracking ensures alternative assignments are tried before concluding impossibility.

Complexity discussion

Time complexity (high-level)

• Worst-case upper bound: (O(m^n)) (trying up to (m) choices per vertex across (n) vertices).
• Notes that pruning via safety checks can reduce it in practice, but the complexity reasoning is presented as worst-case style.

Space complexity

• Uses:
  • Color array: (O(n))
  • Recursion depth: up to (O(n))
• So auxiliary space is (O(n)) (excluding graph storage).

Speaker / sources featured

• Speaker/author (YouTube channel host): an instructor referred to as “Striver” / “Trevor” in the narration (implying a single presenter).
• Source mentioned: “SDE sheet” (problem set reference).
• Additional external source mentioned: Unacademy (event promotion, including “registration link”, “Unacademy app”, and a scheduled live session).