<h2>Short version</h2>
<p>Use sets instead of lists for keeping track of colors</p>
<h2>Long version</h2>
<p>It is known that a greedy coloring will use at most <span class="math-container">$\Delta+1$</span> colors where <span class="math-container">$\Delta$</span> is the maximum degree of any node. Initialize each node with the same set of <span class="math-container">$\Delta+1$</span> colors.</p>
<p>When you color a node <span class="math-container">$u$</span>, remove its color from the color set of each of its neighbors (and you can remove <span class="math-container">$u$</span> from the graph). Now choosing a color for each new uncolored node takes constant time, since you ca pop any color from its color set which includes all the colors that have not been removed due to one of its previously colored neighbors.</p>
<p>For each neighbor, removing the color of <span class="math-container">$u$</span> from its color set takes <span class="math-container">$O(1)$</span> (assuming no collisions in the hash table implementing the set).</p>
<p>Hence, for each node <span class="math-container">$u$</span>, it takes <span class="math-container">$O(1)$</span> to color it and <span class="math-container">$O(\Delta)$</span> to update all of its neighbors' color sets once <span class="math-container">$u$</span> is colored. This gives the runtime <span class="math-container">$O(n\Delta)$</span>.</p>
<p>Notice that each edge is used exactly twice when coloring nodes, and both operations using the edge are <span class="math-container">$O(1)$</span> (either removing a color from the neighbor's set, or skipping the neighbor because it is already colored). Therefore, we also get a runtime of <span class="math-container">$O(n+m)$</span>.</p>

CC BY-SA 4.0
2023-04-16T07:56:05.670Z
Initializing a set of size $\Delta+1$ for each vertex already takes time $\Theta(n\Delta)$.
Tassle
CC BY-SA 4.0
2024-01-26T17:54:42.457Z
Greedy colouring is meant to choose the *smallest* colour available for each node. Getting the smallest colour remaining in a set is not an $O(1)$ operation. It is $O(\Delta)$ if order is not maintained. Or, it could be $O(1)$ if you use $O(\log{\Delta})$-cost update operations to maintain ordered sets or a min-heap.
JimN
CC BY-SA 4.0
2023-04-16T05:38:03.423Z
2023-04-16T05:39:32.333Z
2023-04-16T05:39:32.333Z
bja
<p>In most resources I could find, greedy algorithm is described as follows:
for every vertex <span class="math-container">$v$</span>, assign the minimal color not used by its neighbors.</p>
<p>The above could be implemented as:</p>
<pre><code>colors[] &lt;- 0 #assuming that 0 = not colored
for v in V:
  used[] &lt;- false
  for u in N(v):
    if colors[u] != 0:
      used[colors[u]] &lt;- true
  k &lt;- 0
  while used[k] != 0:
    k &lt;- k + 1
  colors[v] &lt;- k + 1 
return colors
</code></pre>
<p>It is a similar algorithm to the one presented here: <a href="https://cstheory.stackexchange.com/a/11147/69014">https://cstheory.stackexchange.com/a/11147/69014</a>, where the author states that its time complexity is <span class="math-container">$O(n + m)$</span>. I don't understand how is that possible as the outermost loop iterates <span class="math-container">$n$</span> times and the inner <em>while</em> loop might take up to <span class="math-container">$\Delta$</span> iterations before finding the first unused color, hence resulting in <span class="math-container">$O(n\Delta)$</span> time complexity.</p>
<p>How could you achieve linear time complexity?</p>

CC BY-SA 4.0
2023-04-16T08:23:01.367Z
When considering a vertex of degree $d$, there are at most $d$ colors used by its neighbours. This means that the inner while loop will run at most $d$ times before reaching an unused value. It also means that you can take the array "used" to be of length $d+1$ (simply ignore colors greater than that in the inner for loop).
Tassle
CC BY-SA 4.0
2023-04-16T09:04:46.853Z
@Tassle doesn't it imply that the total time complexity is $O(n\Delta)$ just as I stated in the question? Reducing *used* array only affects the space used.
Sebastian Szczepański
CC BY-SA 4.0
2023-04-16T09:17:28.493Z
Oh, I guess I see it. Two inner for loops is essentially edge traversal (each edge twice to be precise). Since inner *while* takes as much iterations as inner *for*, it does not affect the resulting time complexity of $O(m)$. We also need to zero-initialize *colors* array beforehand, hence $O(n + m)$. Is that correct? Was it linear all along?
Sebastian Szczepański
CC BY-SA 4.0
2023-04-16T15:57:03.160Z
Yes, that was where I was going. It was already linear (as long as you are carefull to only initialize an array of length $O(d)$ for "used")
Tassle
CC BY-SA 4.0
2023-04-16T16:03:53.607Z
Sure thing, thanks for pointing me in the right direction. Write an answer if you want and I’ll accept it.
Sebastian Szczepański
<graph-algorithms><time-complexity><graph-colouring><greedy-algorithms>
How do you achieve linear time complexity of greedy graph coloring?
Sebastian Szczepański
# How do you achieve linear time complexity of greedy graph coloring?

(Asked by: username_0 on 2023-04-15)

In most resources I could find, greedy algorithm is described as follows:
for every vertex $v$, assign the minimal color not used by its neighbors.
The above could be implemented as:
colors[] <- 0 #assuming that 0 = not colored
for v in V:
  used[] <- false
  for u in N(v):
    if colors[u] != 0:
      used[colors[u]] <- true
  k <- 0
  while used[k] != 0:
    k <- k + 1
  colors[v] <- k + 1 
return colors

It is a similar algorithm to the one presented here: https://cstheory.stackexchange.com/a/11147/69014, where the author states that its time complexity is $O(n + m)$. I don't understand how is that possible as the outermost loop iterates $n$ times and the inner while loop might take up to $\Delta$ iterations before finding the first unused color, hence resulting in $O(n\Delta)$ time complexity.
How could you achieve linear time complexity?

**Tags:** graph-algorithms, time-complexity, graph-colouring, greedy-algorithms

> **Comments:**
> **username_1**: When considering a vertex of degree $d$, there are at most $d$ colors used by its neighbours. This means that the inner while loop will run at most $d$ times before reaching an unused value. It also means that you can take the array "used" to be of length $d+1$ (simply ignore colors greater than that in the inner for loop).  
> **username_0**: @username_1 doesn't it imply that the total time complexity is $O(n\Delta)$ just as I stated in the question? Reducing *used* array only affects the space used.  
> **username_0**: Oh, I guess I see it. Two inner for loops is essentially edge traversal (each edge twice to be precise). Since inner *while* takes as much iterations as inner *for*, it does not affect the resulting time complexity of $O(m)$. We also need to zero-initialize *colors* array beforehand, hence $O(n + m)$. Is that correct? Was it linear all along?  
> **username_1**: Yes, that was where I was going. It was already linear (as long as you are carefull to only initialize an array of length $O(d)$ for "used")  
> **username_0**: Sure thing, thanks for pointing me in the right direction. Write an answer if you want and I’ll accept it.  

---

## 1 answers

### Answer by username_2 on 2023-04-16. Score: -1

## Short version

Use sets instead of lists for keeping track of colors

## Long version

It is known that a greedy coloring will use at most $\Delta+1$ colors where $\Delta$ is the maximum degree of any node. Initialize each node with the same set of $\Delta+1$ colors.

When you color a node $u$, remove its color from the color set of each of its neighbors (and you can remove $u$ from the graph). Now choosing a color for each new uncolored node takes constant time, since you ca pop any color from its color set which includes all the colors that have not been removed due to one of its previously colored neighbors.

For each neighbor, removing the color of $u$ from its color set takes $O(1)$ (assuming no collisions in the hash table implementing the set).

Hence, for each node $u$, it takes $O(1)$ to color it and $O(\Delta)$ to update all of its neighbors' color sets once $u$ is colored. This gives the runtime $O(n\Delta)$.

Notice that each edge is used exactly twice when coloring nodes, and both operations using the edge are $O(1)$ (either removing a color from the neighbor's set, or skipping the neighbor because it is already colored). Therefore, we also get a runtime of $O(n+m)$.

> **Comments:**
> **username_1**: Initializing a set of size $\Delta+1$ for each vertex already takes time $\Theta(n\Delta)$.  
> **username_3**: Greedy colouring is meant to choose the *smallest* colour available for each node. Getting the smallest colour remaining in a set is not an $O(1)$ operation. It is $O(\Delta)$ if order is not maintained. Or, it could be $O(1)$ if you use $O(\log{\Delta})$-cost update operations to maintain ordered sets or a min-heap.  

---

