3
$\begingroup$

Suppose you want to color the vertices of a graph in a greedy fashion, given a predetermined order of these vertices.

I am wondering if these two algorithms are equivalent:

Algorithm 1: Consider each vertex (in the given order) and assign the smallest color available.

Algorithm 2: While all vertices are not colored, sequentially build color classes by trying to include vertices (in the given order) in the current class.

I am almost sure that these two algorithms are equivalent, but a confirmation would be great! Thanks.

$\endgroup$
4
  • $\begingroup$ In the second algorithm, do you mean that if you cannot place the next vertex in one of the existing classes, then you use it to start a new class? If so, this is indeed equivalent to the first algorithm, provided that you then assign the smallest color to the first color class, the next smallest color to the second color class, and so on. $\endgroup$ Nov 4, 2015 at 1:50
  • $\begingroup$ yes that is exactly what I mean. Is there a way to prove this? Simple examples suggest it is true, but I cannot manage to write a generic one as a proof. $\endgroup$
    – Kuifje
    Nov 4, 2015 at 4:10
  • 1
    $\begingroup$ A rather standard way to prove this kind of equivalence is to look for the first vertex that would be assigned a different color by the algorithms. A slightly more formal description of the algorithms is desirable though. $\endgroup$ Nov 4, 2015 at 7:56
  • $\begingroup$ I an having a hard time understanding how algorithm 2 works. I would like to help you. Please provide an example and/or another explanation with some steps. $\endgroup$
    – user799688
    Dec 2, 2020 at 7:13

1 Answer 1

2
+50
$\begingroup$

Assuming that your second algorithm does the following: For each colour $i\in [1,c]$ in order, go through the vertices $v_1,\ldots, v_n$ in order and assign to a vertex the colour $i$ if it is not already coloured, and no neighbour of it has colour $i$.

Let us suppose for contradiction that algorithm II doesn't produce the same colouring as algorithm I, let us call these colourings $c_1$ and $c_2$. There is some smallest colour $i$ which appears in the wrong place, and some smallest vertex $v_j$ given the colour $i$ by algorithm II where algorithm I give $v_j$ a different colour. That is $c_2(v_j) = i$ and $c_1(v_j) \neq i$. That is, we assume that for all $i'<i$ and $v_k$ if $c_1(v_k)=i'$, then $c_2(v_k)=i'$ and also if $v_k < v_j$ and $c_1(c_k) = i$, then $c_2(v_k)=i$.

However, since $c_1(v_j) \neq i$ either there is a neighbour $v_k$ of $v_j$ with $v_k < v_j$ and $c_1(v_k)=i$ or $c_1(v_j)=i' < i$ and so $v_j$ has no neighbour coloured $i'$ in $c_1$. In the first case, $c_2(v_k)=i$ and so we can't also colour $c_2(v_j)=i$, contradicting our assumption. In the second case we can conclude that $v_j$ has no neighbour coloured $i'$ in $c_1$ and hence no neighbour coloured $i'$ in $c_2$, and so when we tried to colour $v_j$ with colour $i'$ in algorithm II, which happens before we try to colour it with colour $i$, we were succesful, again contradiction our assumption.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.