<p>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).</p>

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

CC BY-SA 3.0
2012-04-20T16:21:32.370Z
but still, using the edge representation, wouldn't it have to be O(mn)?
Jonny5
CC BY-SA 3.0
2012-04-20T16:27:34.933Z
@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
CC BY-SA 3.0
2012-04-20T16:51:46.763Z
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?
Jonny5
CC BY-SA 3.0
2012-04-20T16:16:11.783Z
2012-04-21T06:58:10.247Z
2012-04-21T06:58:10.247Z
sxu
<p>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] &gt; 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] &gt; 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.</p>

CC BY-SA 3.0
2012-04-20T17:06:31.423Z
2012-04-20T18:58:16.997Z
2012-04-20T18:58:16.997Z
Volker Turau
<p>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 &amp; lower/upper bounds but also the difficulty of establishing precise estimates.</p>

<p>[1] <a href="http://theory.stanford.edu/~tomas/col.ps" rel="nofollow noreferrer">online algorithms for edge coloring by Feder, Motwani, Panigrahy</a></p>

<p>[2]
<a href="https://cstheory.stackexchange.com/questions/10088/can-this-randomized-greedy-algorithm-be-made-online-or-being-proved-impossible/10125#10125">Can this randomized greedy algorithm be made online? Or being proved impossible?</a></p>

CC BY-SA 3.0
2012-04-25T03:26:59.007Z
2012-04-25T03:26:59.007Z
2017-04-13T12:32:28.053Z
vzn
<p>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²).</p>

CC BY-SA 4.0
2023-09-09T10:28:45.630Z
2023-09-09T10:28:45.630Z
Markus
<p>I was looking at some heuristics for coloring and found this book on Google books: <a href="http://books.google.be/books?id=nEmcID52qtsC&amp;lpg=PP1&amp;dq=graph%20coloring&amp;pg=PA16#v=onepage&amp;q=greedy&amp;f=false" rel="nofollow">Graph 
Colorings By Marek Kubale</a></p>

<p>They describe the Greedy algorithm as follows:</p>

<pre><code>While there is an uncolored vertex v
    choose a color not used by its neighbors and assign it to v
</code></pre>

<p>Then they describe a sequential algorithm:</p>

<pre><code>order the vertices in a random way
execute the greedy algorithm
</code></pre>

<p>They claim that this algorithm is $O(m+n)$.  </p>

<p>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)</p>

<ds.algorithms><graph-theory><time-complexity><graph-colouring><greedy-algorithms>
Complexity of greedy coloring
Jonny5
# Complexity of greedy coloring

(Asked by: username_0 on 2012-04-20)

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)

**Tags:** ds.algorithms, graph-theory, time-complexity, graph-colouring, greedy-algorithms

---

## 4 answers

### Answer by username_1 on 2012-04-20. Score: 5

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

> **Comments:**
> **username_0**: but still, using the edge representation, wouldn't it have to be O(mn)?  
> **username_1**: @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.  
> **username_0**: 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?  

---

### Answer by username_2 on 2012-04-20. Score: 3

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.


---

### Answer by username_3 on 2012-04-25. Score: 0

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.

[1] [online algorithms for edge coloring by Feder, Motwani, Panigrahy](http://theory.stanford.edu/~tomas/col.ps)

[2]
[Can this randomized greedy algorithm be made online? Or being proved impossible?](https://cstheory.stackexchange.com/questions/10088/can-this-randomized-greedy-algorithm-be-made-online-or-being-proved-impossible/10125#10125)


---

### Answer by username_4 on 2023-09-09. Score: -2

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


---

