Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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 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 at 15:48
    
I missed the colour numbering constraint, sorry. –  Arthur Jun 16 at 15:51

1 Answer 1

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|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 at 16:18
    
THANK YOU:) i will see to it and try to implement –  savvi singh Jun 16 at 16:24

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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