# 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)

The book probably assumes an adjacency list representation. Each vertex is visited once, so to decide what color it should get, all its neighbors are checked, so each edge is crossed twice (once in each direction).

If you have an adjacency matrix representation, I think it will be $O(n^2)$.

• but still, using the edge representation, wouldn't it have to be O(mn)? Commented Apr 20, 2012 at 16:21
• @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
Commented Apr 20, 2012 at 16:27
• Ok, I think I get it: am I correct to conclude that the complexity of the greedy part is O(m+n)? Because there are n assignments and 2m edge lookups? But then, if the graph is connected, we have m >= n-1 and we arrive at O(m). Is this correct? Commented Apr 20, 2012 at 16:51

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.

there is some extended analysis of the greedy coloring algorithm complexity in this recent paper[1] and some further commentary in [2] that should give an idea about the style of complexity estimation & lower/upper bounds but also the difficulty of establishing precise estimates.

For me it got easier to understand once I explained to myself that for a fully connected graph m = n*(n-1)/2. I.e. in the worst case O(n+m) converges to O(n²).