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?