Find a lesson, question or project

Start typing to search published content and planned structures.

↑ ↓ moveEnter openEsc close

M-Coloring in Java: Can Every Neighbor Have a Different Color?

Solve graph coloring with tentative assignments, neighbor checks and backtracking; understand why a triangle needs three colors.

MediumRecursion and backtrackingPattern: recursion, backtracking

Problem statement

Can we assign at most m colors to an undirected graph so that the endpoints of every edge have different colors? Return true or false. This is vertex coloring, not coloring edges and not finding the minimum number of colors.

The teaching input uses vertices 0..n−1 and an edge list. Every edge is an undirected pair. Vertices without edges are still part of the graph. A color may be reused by vertices that are not neighbors, and not every available color must be used.

Practice on GFG M-Coloring; adapt the judge wrapper if necessary. The implementation below performs the actual coloring search. No unverified numeric graph-size limit is added.

Constraints & requirements

CONTRACT
Use vertices 0..n−1 and valid two-endpoint edges. Zero means uncolored; real colors are 1..m. Isolated vertices still need a color. Self-loops are rejected defensively; no unverified numeric size bound is claimed.

Examples 3 test cases

  1. Example 1 Case 1

    Input
    n=4; m=3; edges=[[0,1],[1,2],[2,3],[3,0],[0,2]]
    Output
    true

    One valid assignment is [1,2,3,2]. Check all five edges, not just the outer cycle.

  2. Example 2 Case 2

    Input
    n=4; m=2; same edges
    Output
    false

    Vertices 0,1,2 form a triangle, which cannot share only two colors.

  3. Example 3 Case 3

    Input
    n=3; m=1; edges=[]
    Output
    true

    Vertices are isolated, so the same color is allowed on all three.

Solve on GeeksforGeeks ↗

Hints Optional

Hints become more specific one step at a time.
01Hint 1

Give one vertex a tentative color, then solve the remaining vertices.

02Hint 2

Reject a color already used by any colored neighbor; build both directions of every edge.

03Hint 3

Undo after failure and try another color; one complete consistent assignment is enough.

How to think before coding

Let colors[v]=0 mean not assigned and colors 1..m be real choices. One call assigns vertex v, not one connected component. Try a safe color, ask vertex v+1 to finish, and reset v after failure. If v==n, all vertices are assigned. A true child ends an existence search; a false child means try another color, not give up on all assignments.

Brute force and the improvement

Try every complete assignment of m colors to n vertices and then check every edge. There are m^n assignments; constructing/checking each gives an O((n+E)·m^n) bound and O(n) working color storage, excluding graph storage. A single equal-colored edge invalidates an entire assignment, so waiting until the end is wasteful. Check each tentative color against already-colored neighbors immediately. Backtracking prunes conflicts and stops at the first complete valid assignment, but graph coloring remains exponential in general.

Intuition: a safe choice now may fail later

Give the first vertex a tentative color. For the next vertex, try a color different from its already-colored neighbors. Continue until every vertex has a color.

If a vertex has no legal color, the earlier choices may be responsible. Return false to the waiting caller. That caller removes its tentative color and tries another one. A local safety check is not a promise that all remaining vertices can be colored.

For the supplied four-vertex graph, edges 0–1, 1–2 and 0–2 form a triangle. With two colors, after 0 receives 1 and 1 receives 2, vertex 2 cannot use either. With three colors, it can use 3; vertex 3 can then use 2.

Algorithm

  1. Build adjacency lists, inserting both directions of every edge.
  2. Initialize every entry in colors to 0, meaning uncolored.
  3. At vertex, try colors 1 through m.
  4. Reject a color used by a neighbor; otherwise assign it and recurse to vertex+1.
  5. Return immediately after one complete successful assignment.
  6. After failure, reset this vertex to 0 and try the next color.

The vertex index advances even for isolated vertices. We are assigning the entire graph, not doing a traversal starting from only one connected component.

Java solution

All search state belongs to this invocation, so repeated calls are independent. A self-loop is rejected because its endpoint cannot differ from itself. Valid indexed edges are assumed.

Java
import java.util.*;

class Solution {
    public static boolean graphColoring(int[][] edges, int m, int n) {
        List<List<Integer>> graph = new ArrayList<>(); // Undirected adjacency lists.
        for (int v = 0; v < n; v++) graph.add(new ArrayList<>()); // Include isolated vertices too.
        for (int[] edge : edges) {
            if (edge[0] == edge[1]) return false; // A self-loop cannot have differently colored endpoints.
            graph.get(edge[0]).add(edge[1]); graph.get(edge[1]).add(edge[0]); // Store BOTH directions.
        }
        return colorVertex(0, m, graph, new int[n]); // Zero means uncolored; colors are 1..m.
    }
    private static boolean colorVertex(int vertex, int m, List<List<Integer>> graph, int[] colors) {
        if (vertex == graph.size()) return true; // Every vertex now has a consistent color.
        for (int color = 1; color <= m; color++) {
            boolean safe = true;
            for (int neighbor : graph.get(vertex)) {
                if (colors[neighbor] == color) { safe = false; break; } // Already colored neighbor conflicts.
            }
            if (!safe) continue; // Never recurse after violating an edge constraint.
            colors[vertex] = color; // Reserve a color for this branch.
            if (colorVertex(vertex + 1, m, graph, colors)) return true; // One complete assignment is enough.
            colors[vertex] = 0; // Failure: undo before trying another color.
        }
        return false; // No color extends the current partial assignment.
    }

    public static void main(String[] args) {
        int[][] edges = {{0,1},{1,2},{2,3},{3,0},{0,2}};
        System.out.println(graphColoring(edges, 3, 4)); // true
        System.out.println(graphColoring(edges, 2, 4)); // false
    }
}

The invocation prints true for three colors and false for two. Color numbers are just names: changing every 1 to red and every 2 to blue changes no constraint.

Recursion tree and dry run

Numbered illustrated dry run for M-Coloring; the text transcript explains the states.
Follow the numbered panels in order. Open full-size dry run ↗
Read the text transcript

Follow the Java, step by step

Example: n = 3, m = 2, edges = [[0,1],[1,2],[0,2]]

What to track: This triangle demonstrates failure and undo. colors[v] = 0 means uncolored; colors 1 and 2 are the only allowed choices.

  1. Choose a color for vertex 0

    Java operationcolors[vertex] = color;
    Statevertex = 0; color = 1; colors = [1,0,0]

    Its neighbors are uncolored, so assigning 1 is locally safe. Recursion advances to vertex 1.

  2. Reject an equal neighbor color

    Java operationif (colors[neighbor] == color) { safe = false; break; }
    Statevertex = 1; attempted color = 1 conflicts with vertex 0

    No child is created for this conflict. Trying color 2 gives colors = [1,2,0].

  3. Exhaust vertex 2

    Java operationif (!safe) continue;
    Statevertex = 2; color 1 conflicts with vertex 0; color 2 conflicts with vertex 1

    Both permitted colors are unsafe. This call returns false without assigning a color.

  4. Undo the waiting assignments

    Java operationcolors[vertex] = 0;
    Statevertex-1 caller restores [1,0,0]; it has no more colors; vertex-0 caller restores [0,0,0]

    Each failed continuation tells its parent to release its own reservation before trying another color.

  5. Try the other root color

    Java operationif (colorVertex(vertex + 1, m, graph, colors)) return true;
    Stateroot chooses 2; vertex 1 can only choose 1; vertex 2 again has neither color available

    Swapping the names 1 and 2 does not remove the triangle conflict. Both root branches fail.

  6. Return the exhausted-search result

    Java operationreturn false;
    Statecolors restored to [0,0,0]; no complete assignment was reached

    With m = 3 a third color would let vertex 2 complete the assignment. The trace here deliberately uses m = 2.

Final result: false: three mutually adjacent vertices cannot use only two colors.

Worked example · read from top to bottom
m=3, colors initially [0,0,0,0]
vertex 0: try 1 → [1,0,0,0]
  vertex 1: 1 conflicts with 0; try 2 → [1,2,0,0]
    vertex 2: 1 conflicts with 0; 2 conflicts with 1
              try 3 → [1,2,3,0]
      vertex 3: 1 conflicts with 0; try 2 → [1,2,3,2]
        vertex 4: all vertices assigned → true
      true returns through every waiting caller

Check the five edges: 0–1 is 1/2, 1–2 is 2/3, 2–3 is 3/2, 3–0 is 2/1 and 0–2 is 1/3. Vertices 1 and 3 may share color 2 because no edge joins them.

With m=2, vertex 2 fails. Its caller clears vertex 1. Eventually the root also tries color 2 and encounters the symmetric failure. Returning false requires exhausting all compatible choices, not merely failing with the first color.

Why it works

Before a call, all earlier vertices are colored consistently. A candidate is accepted only if it differs from every colored neighbor. This preserves consistency; edges to uncolored vertices will be checked when those vertices receive colors.

Each color choice is tried, so any valid assignment has a matching path through the search. Reaching vertex n proves that all vertices and all edge constraints are covered. Resetting a failed choice restores the parent’s state before the next sibling.

Complexity and alternative approaches

With V vertices, E edges and m colors, there can be m^V complete assignments. A neighbor check takes up to the maximum degree Δ. A conservative bound is O(V+E + V·max(1,Δ)·m^V), counting intermediate attempts as well as adjacency construction. Early success and conflict pruning reduce actual work; they do not make the general problem linear.

Adjacency storage uses O(V+E). Colors and recursive frames use O(V) extra space. No list of all assignments is returned.

For two colors, a bipartite BFS/DFS check is faster: O(V+E). It is not a general solver for arbitrary m. Reordering vertices by constraints can improve practical backtracking, but greedy coloring alone can use too many colors and is not a reliable feasibility decision.

Common mistakes

  • Forgetting the reverse adjacency entry for an undirected edge.
  • Treating 0 as a usable color when it means unassigned.
  • Checking only one connected component or skipping isolated vertices.
  • Returning false after the first forbidden color instead of trying the rest.
  • Confusing “at most m” with “must use exactly m.”

Practice next

Next lessonN-Queens

Back to Recursion and backtracking →