

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer

Given a directed graph such that each node has indegree=outdegree=1 devise a algo that colour the graph such that no adjacent nodes has same color. **Note:**there is no self loop and graph has to be colored using atmost 3 colors. Also the number of color 1, the number of color 2 and the number of color 3 should differ by at most one.

Example: 1->2, 2->3 , 3->4 ,4->1 is the graph then one possible color scheme is :

1=red 2=blue 3=green 4=blue

Total red=1 blue=2 green=1 hence atmost dofference is 1 only therefore satisfies the constraint.

I am thinking of greedy approach:1. Color a vertex with color 1. 2. Pick an uncolored vertex v. Color it with the lowest-numbered color that has not been used on any previously-colored vertices adjacent to v. 3. Repeat the previous step until all vertices are colored

But will this approach give right coloring scheme always??

share|cite|improve this question
If the graph is finite and indegree=outdegree=1 on every vertex, the graph is a union of loops. For each loop, chose a starting vertex, go from there and color each vertex using alternatively red and blue. Use green if you have to on the last node of the loop. – Arthur Jun 16 '14 at 15:43
if there is graph like 1->2,2->1,3->4,4->3 how do you do it??also difference between colours used should be atmost 1. – savvi singh Jun 16 '14 at 15:48
I missed the colour numbering constraint, sorry. – Arthur Jun 16 '14 at 15:51
up vote 1 down vote accepted

There are three kinds of loops, going by their number of vertices mod 3. In each case I will assume you're going around the loop using the colours red$\to$green$\to$blue$\to$red and so on, but exactly which colour you start with might differ.

I'm going to number the colours in a loop, with $1$ being the colour you start with. So if red is $1$, green is $2$ and blue is $3$. But if red is $2$ then green is $3$ and blue is $1$. So, going by the number of vertices in a loop mod 3:

  1. In this case, the last vertex will have colour number $1$, which is illegal. THe second-to-last will have colour $3$, so the one available colour for the last node is $2$. In this case, there is one more node of colour $2$ than of the two others.

  2. In this case, there will be one less vertex of colour number $3$ when you're done.

  3. These loops will contain just as many of one colour an any other, and it won't matter which colour you start with.

Do all the type 3 loops first, since they don't really matter. Then start pairing up type 1 and 2 loops. In each pair, do the type one loop, then do the type 2 loop starting with colour number $3$ of the type 1 loop. They will then cancel out.

Now, either you have too many type 1 loops, or you have too many type 2 loops, it doesn't matter. Just do the rest of them, alternating which colour you start with.

share|cite|improve this answer
Your loop $1\to2\to3\to4\to1$ is of type 1. If you have $1\to2\to1$ and $3\to4\to3$, then that's two type 2 loops. – Arthur Jun 16 '14 at 16:18
THANK YOU:) i will see to it and try to implement – savvi singh Jun 16 '14 at 16:24

Your Answer


