Graph Coloring Backtrack

Determine if an undirected graph can be colored with k colors using backtracking.

backtracking graphs coloring constraint-satisfaction

Write a function `can_color(graph, k)` that takes an adjacency list representation of an undirected graph and a positive integer `k`, and returns `True` if the vertices can be colored using at most `k` colors such that no two adjacent vertices have the same color. Otherwise, return `False`.

The graph is given as a list of lists: `graph[i]` is a list of integers representing the neighbors of vertex `i`. Vertices are numbered `0` to `n-1` where `n == len(graph)`. The graph is simple (no self-loops, no multiple edges) and undirected (if `j` is in `graph[i]`, then `i` is in `graph[j]`).

You must implement a backtracking algorithm that attempts to assign a color (1, 2, ..., k) to each vertex in order, checking compatibility with already colored neighbors. The order of vertices should be from 0 to n-1.

Return `True` if a valid coloring exists, otherwise `False`.

Constraints

- `1 <= len(graph) <= 12` (small enough for backtracking).
- `0 <= graph[i][j] < len(graph)` for all i.
- `1 <= k <= 4`.
- The graph is undirected and simple.
- Time complexity should be O(k^n) in worst case, but pruning reduces it.

Example

```python
>>> can_color([[1], [0, 2], [1]], 2)
True
>>> can_color([[1], [0, 2], [1]], 3)
True
>>> can_color([[1,2], [0,2], [0,1]], 2)
False
>>> can_color([[]], 1)
True
```

30 points ~30 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think of a recursive function that tries to assign a color to the next vertex.

Check if a color is valid by ensuring no neighbor already assigned that color.

Backtrack when a color assignment leads to a dead end.

If you successfully assign a color to every vertex, return True.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.