# Complexity of greedy coloring

I was looking at some heuristics for coloring and found this book on Google books: Graph Colorings By Marek Kubale

They describe the Greedy algorithm as follows:

While there is an uncolored vertex v
choose a color not used by its neighbors and assign it to v


Then they describe a sequential algorithm:

order the vertices in a random way
execute the greedy algorithm


They claim that this algorithm is $O(m+n)$.

Its seems to me that the greedy algorithm is in fact $O(n^2)$. Am I missing something here? Or is the greedy method $O(m)$? ($m$ = edges, $n$ = vertices)

If you have an adjacency matrix representation, I think it will be $O(n^2)$.
• @Xaero182 The adjacency list of a vertex only has size equal to the number of its neighbors, so we do not look at ALL the edges for each vertex (that would be $O(mn)$), only edges incident to it, and an edge is incident to two vertices, so it is looked at twice. – sxu Apr 20 '12 at 16:27
A careless implementation of the greedy coloring algorithm leads to a $O(n\Delta)$ algorithm. With some care it can easily be implemented in linear time $O(n+m)$. Create an array $used$ with $\Delta + 1$ components and an array $colors$ of length $n$. Initialize $colors$ and $used$ with 0. Now iterate over all nodes. For each node $v$ iterate over the neighbors $w$ of $v$. If $color[w] > 0$ (i.e. $w$ is already colored) set $used[color[w]]=1$. Then sequentially search the minimal k such that $used[k] == 0$. This is the color of $v$, i.e. $color[v] = k$. Then iterate again over the neighbors $w$ of $v$. If $color[w] > 0$ then set $used[color[w]] == 0$. Upon termination $color$ is a valid coloring. The algorithm obviously requires only $O(n+m)$ time. You can find detailed source code in my book on graph algorithms, but that is in German.