How do you achieve linear time complexity of greedy graph coloring?

Question

In most resources I could find, greedy algorithm is described as follows: for every vertex $v$, assign the minimal color not used by its neighbors.

The above could be implemented as:

colors[] <- 0 #assuming that 0 = not colored
for v in V:
  used[] <- false
  for u in N(v):
    if colors[u] != 0:
      used[colors[u]] <- true
  k <- 0
  while used[k] != 0:
    k <- k + 1
  colors[v] <- k + 1 
return colors

It is a similar algorithm to the one presented here: https://cstheory.stackexchange.com/a/11147/69014, where the author states that its time complexity is $O(n + m)$. I don't understand how is that possible as the outermost loop iterates $n$ times and the inner while loop might take up to $\Delta$ iterations before finding the first unused color, hence resulting in $O(n\Delta)$ time complexity.

How could you achieve linear time complexity?

Answer 1

Short version

Use sets instead of lists for keeping track of colors

Long version

It is known that a greedy coloring will use at most $\Delta+1$ colors where $\Delta$ is the maximum degree of any node. Initialize each node with the same set of $\Delta+1$ colors.

When you color a node $u$, remove its color from the color set of each of its neighbors (and you can remove $u$ from the graph). Now choosing a color for each new uncolored node takes constant time, since you ca pop any color from its color set which includes all the colors that have not been removed due to one of its previously colored neighbors.

For each neighbor, removing the color of $u$ from its color set takes $O(1)$ (assuming no collisions in the hash table implementing the set).

Hence, for each node $u$, it takes $O(1)$ to color it and $O(\Delta)$ to update all of its neighbors' color sets once $u$ is colored. This gives the runtime $O(n\Delta)$.

Notice that each edge is used exactly twice when coloring nodes, and both operations using the edge are $O(1)$ (either removing a color from the neighbor's set, or skipping the neighbor because it is already colored). Therefore, we also get a runtime of $O(n+m)$.