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??