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)$.