3

Suppose you want to color the vertices of a graph in a greedy fashion, given a predetermined order of these vertices. The goal is to avoid giving two adjacent (linked by an edge) vertices the same color.

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 not all vertices are colored, sequentially build color classes by trying to include uncolored, non-adjacent vertices (in the given order) in the current class.

I am almost sure that these two algorithms are equivalent. Indeed, consider Algorithm 2 on a graph with 5 vertices. Suppose the first color class has vertices 1, 3, 5. This means that vertices 2 and 4 cannot take color 1. So in Algorithm 1, vertex 1 would take color 1, vertex 2 would take color 2, vertex 3 would take color 1, vertex 4 would take color 2 or 3, and vertex 5 would take color 1. This simple example convinces me it is true, but of course it is not a proof. Can we transform it into a proof by making it more generic, or can we find a counter example?

  • 1
    Sharing your research helps everyone. Tell us what you've tried and why it didn’t meet your needs. This demonstrates that you’ve taken the time to try to help yourself, it saves us from reiterating obvious answers, and most of all it helps you get a more specific and relevant answer. Also see How to Ask – gnat Nov 3 '15 at 23:15
  • Your question description is missing something - are you talking about an algorithm for coloring vertices so every two connected vertices get a different color? – Doc Brown Nov 4 '15 at 6:44
  • 1
    @gnat: after the last edit, the OP tried indeed to tell us what he had tried to solve the problem. But the description is IMHO too incomplete to give him a reasonable answer. – Doc Brown Nov 4 '15 at 10:20
  • This question may also be a fit for math or cs stack exchanges – Daenyth Nov 4 '15 at 12:50
  • @DocBrown Indeed, by "available color" I mean one that does not color two adjacent (linked by an edge) vertices. – Kuifje Nov 4 '15 at 15:01
0

I think you are correct, both algorithms are equivalent. Look which of the vertices of an arbitrary graph get the first (smallest) color C1 from both algorithms. It is easy to see that those are the same, because both algorithms do essentially the same - iterate over the vertices in the given order, assign either C1 or

  • a different color (algorithm 1)

  • no color (algorithm 2)

to a vertex, with the constraint to use C1 when the next vertice is not adjacent to a formerly C1-colored vertex.

Now you can apply the same argument for the next color C2, using all not C1-colored vertices, then C3 and so on, which leads you inductively to the same total coloring.

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.