Coloring a Graph with Maximum Degree D Using D+1 Colors

Problem

Given an undirected graph with maximum degree D, color the graph using at most D+1 colors so that no two adjacent nodes have the same color.

Examples

Example 1

graph LR;
  A(a) --- B(b) --- C(c)

  %% color definitions (fill, stroke)
  classDef red fill:#ffb3b3,stroke:#cc0000,stroke-width:1px;
  classDef green fill:#b3ffb3,stroke:#00aa00,stroke-width:1px;

  class A red;
  class B green;
  class C red;

Input:
adj = 
{
  'a': ['b'],
  'b': ['a', 'c'],
  'c': ['b']
}
d = 2
colors = [red, green, blue]
Output: {'a': 'red', 'b': 'green', 'c': 'red'}
Explanation: No two adjacent nodes have the same color, and only 2 colors are used.

Example 2

graph LR;
  A(0) --- B(1)
  A --- C(2)
  A --- D(3)
  B --- C

  %% color definitions
  classDef red fill:#ffb3b3,stroke:#cc0000,stroke-width:1px;
  classDef green fill:#b3ffb3,stroke:#00aa00,stroke-width:1px;
  classDef blue fill:#b3d9ff,stroke:#0066cc,stroke-width:1px;

  class A red;
  class B green;
  class C blue;
  class D green;

Input:
adj = 
{
  0: [1, 2, 3],
  1: [0, 2],
  2: [0, 1],
  3: [0]
}
d = 3
colors = [red, green, blue, yellow]
Output: {0: 'red', 1: 'green', 2: 'blue', 3: 'green'}
Explanation: No two adjacent nodes have the same color, and at most D+1 colors are used.

Solution

Method 1 – Greedy Approach

Intuition & Guarantee

If a graph has maximum degree D, then D+1 colors are always enough to color it so that no two adjacent nodes share a color. This is because each node has at most D neighbors, so there is always at least one available color among D+1 choices. This is a special case where a simple greedy algorithm is guaranteed to work (see also Brooks' theorem).

A brute-force approach would try all possible colorings, which is exponential in the number of nodes. However, for D+1 colors, a greedy algorithm is both correct and efficient: color each node one by one, always picking the first available color not used by its neighbors.

Edge Cases:

• Self-loops: If a node has an edge to itself, legal coloring is impossible (should throw an error).
• Isolated nodes: Can be colored with any color.
• Cycles: Handled naturally by the greedy approach.

This approach is optimal for D+1 colors, but finding the minimum number of colors (the chromatic number) is NP-complete (see the "Graph Coloring Problem" note for more theory and examples).

Approach

1. For each node, check if it has a self-loop (neighbor to itself). If so, coloring is impossible.
2. For each node, collect the colors used by its neighbors.
3. Assign the first available color (from the D+1 color set) not used by its neighbors.
4. Repeat for all nodes.

Code

C++

class Solution {
public:
  void colorGraph(std::unordered_map<int, std::vector<int>>& adj, std::vector<std::string>& colors) {
    for (auto& [u, nbrs] : adj) {
      if (std::find(nbrs.begin(), nbrs.end(), u) != nbrs.end())
        throw std::invalid_argument("Node with self-loop cannot be colored");
      std::unordered_set<std::string> used;
      for (int v : nbrs) if (adj.count(v) && adj[v].size() > 0 && adj[v][0] != "") used.insert(adj[v][0]);
      for (const auto& color : colors) {
        if (!used.count(color)) {
          adj[u].insert(adj[u].begin(), color); // store color at index 0
          break;
        }
      }
    }
  }
};

Java

class Solution {
  public void colorGraph(Map<Integer, List<Integer>> adj, List<String> colors, Map<Integer, String> nodeColors) {
    for (int u : adj.keySet()) {
      if (adj.get(u).contains(u)) throw new IllegalArgumentException("Node with self-loop cannot be colored");
      Set<String> used = new HashSet<>();
      for (int v : adj.get(u)) if (nodeColors.containsKey(v)) used.add(nodeColors.get(v));
      for (String color : colors) {
        if (!used.contains(color)) {
          nodeColors.put(u, color);
          break;
        }
      }
    }
  }
}

Python

class Solution:
  def color_graph(self, adj: dict, colors: list[str]) -> dict:
    node_colors = {}
    for u in adj:
      if u in adj[u]:
        raise ValueError(f"Node {u} has a self-loop and cannot be colored.")
      used = {node_colors[v] for v in adj[u] if v in node_colors}
      for color in colors:
        if color not in used:
          node_colors[u] = color
          break
    return node_colors

Complexity

• ⏰ Time complexity: O(N + M), where N is the number of nodes and M is the number of edges, since each node and edge is processed once.
• 🧺 Space complexity: O(D), where D is the maximum degree, for the set of used colors per node.