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)