391. Graph Colouring - Minimum Number of Colours

Given an undirected graph with n vertices (0-indexed) and m edges, find the minimum number of colors needed to color every vertex such that no two adjacent vertices share a color (the graph's chromatic number).

Input: The first line contains an integer n, the number of vertices. The second line contains an integer m, the number of edges. Each of the next m lines contains two space-separated integers u and v, an undirected edge. Output: Print a single integer - the minimum number of colors needed (the chromatic number).

1 <= n <= 15

A graph with an ODD-length cycle needs AT LEAST 3 colors even though it might superficially look 2-colorable at a glance - always verify with an actual bipartite check (or the full backtracking search) rather than assuming based on appearance.

Find the minimum number of colors needed to color a graph so no two adjacent vertices share a color. Brute force: Try every possible assignment of colors to all n vertices directly for each candidate m - this is what the backtracking check itself does; the OUTER loop trying increasing m values from 1 upward is what finds the true MINIMUM rather than just checking one fixed value. Optimised: Since a graph's chromatic number (minimum colors needed) is a single specific value, testing m=1,2,3,... in increasing order and stopping at the FIRST success directly finds that minimum - a bipartite check (m=2 feasibility) can even serve as a fast initial shortcut, since many practical graphs turn out to only need 2 colors.

For k = 1, 2, 3, ... up to n, generate every possible way of assigning one of k colors to each of the n vertices and check whether any assignment leaves no edge with both endpoints the same color. The first k for which some assignment is valid is the chromatic number. This directly checks the definition of a proper coloring but explores every one of the k^n color assignments for each candidate k. Time: O(n * k^n) in the worst case (k up to n) Space: O(n)

For k = 1, 2, 3, ... up to n, run the classic graph-coloring backtracking routine: color vertices one at a time in order, only trying colors 1..k for each vertex, and immediately abandon a branch as soon as a color choice conflicts with an already-colored neighbor. Stop and report the first k for which the backtracking search finds a complete valid coloring. Pruning invalid partial colorings early makes this far faster in practice than enumerating all k^n assignments, even though the worst case is still exponential. Time: O(k^n) worst case per k, much better in practice Space: O(n)

Since n is at most 15, represent vertex subsets as bitmasks. First determine, for every subset mask, whether it forms an independent set (no two vertices in it are adjacent) by extending the check incrementally from smaller subsets. Then run a subset-cover DP: minColors[0] = 0, and minColors[mask] = 1 + the minimum over every independent, non-empty submask s of mask of minColors[mask XOR s], since one color class must be some independent subset of the remaining vertices. The answer is minColors[(1<<n)-1]. Iterating submasks of every mask costs O(3^n) total, which is fast for n <= 15. Time: O(3^n) time (submask enumeration), plus O(2^n * n) to build independent-set table Space: O(2^n)

1. Write a backtracking check: 'can this graph be properly colored using AT MOST m colors?' by assigning colors one vertex at a time, only using a color if none of its already-colored neighbors use it, backtracking on dead ends. 2. Try m = 1, 2, 3, ... in increasing order, and return the FIRST value for which this feasibility check succeeds. 3. It must succeed by m = n at the latest (every vertex could always get its own unique color).

Time: O(m^n) in the worst case for a single feasibility check at a given m (exponential backtracking), tried for each candidate m from 1 up to the true answer - genuinely expensive, but the small constraint (n<=15) keeps it tractable. Space: O(n), for the color-assignment array and recursion stack.

a graph with no edges (m = 0), an odd-length cycle needing 3 colors despite looking bipartite at a glance, and n at its maximum of 15 to confirm the backtracking search stays feasible.

Be ready to mention that finding the EXACT chromatic number is NP-hard in general - this backtracking-based search is the standard EXACT approach for small n, while much larger graphs would need heuristics or approximations instead.