A graph is said to be bipartite if all its vertices can be partitioned into two
ID: 3765538 • Letter: A
Question
A graph is said to be bipartite if all its vertices can be partitioned into two disjoint subsets X and Y so that every edge connects a vertex in X with a vertex in Y. (One can also say that a graph is bipartite if its vertices can be colored in two colors so that every edge has its vertices colored in different colors; such graphs are also called 2-colorable.) Design either DFS-based or BFS-based algorithm for checking whether a graph is bipartite. Then write a program in C or C++ that will get as input a file with a graph and uses your algorithm to check if it is bipartite. In the case that the graph is found bipartite you program should display the two disjoint subsets. The input is similar as first exercise’s input format.
Explanation / Answer
Assign RED color to the source vertex (putting into set U).
2. Color all the neighbors with BLUE color (putting into set V).
3. Color all neighbor’s neighbor with RED color (putting into set U).
4. This way, assign color to all vertices such that it satisfies all the constraints of m way coloring problem where m = 2.
5. While assigning colors, if we find a neighbor which is colored with same color as current vertex, then the graph cannot be colored with 2 vertices (or graph is not Bipartite)