The question can be restated as follows: Given a graph, is it bipartite?. If yes, find the partition.
A graph is bipartite if and only if there is no odd cycle. The following algo wl find the partition and if there is an odd cycle, it wl report that it is not possible. Level Decompose the graph with respect to some vertex. ( BFS can be used here) ( O(V+E) ) If there is an edge between two vertices which are both in odd or in even depth, return false. ( Running through all the edges ) ( O( E) ) Else return partition 1 = all vertices at odd depth. partition 2 = all vertices at even depth. Overall complexity: O(V+E) I think this answers your question. On Jul 6, 12:37 am, Nitish Garg <nitishgarg1...@gmail.com> wrote: > Can you point me through any tutorial for Graph Coloring? I think CLRS does > not explain graph coloring. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
