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??
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:
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.
In this case, there will be one less vertex of colour number $3$ when you're done.
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.