3.4 Testing Bipartiteness: An Application of Breadth-First Search

A bipartite graph is a graph where one node V can be partitioned into sets X and Y in such a way that every edge has an end in X and another end in Y. If we suppose the nodes of X are colored red and the nodes in Y are colored blue, we can say that a graph is bipartite if it is possible to color its nodes red and blue such that every edge has one red end and one blue end. If a graph is bipartite, then it can not contain an odd cycle. Thus an odd cycle is an obstacle to bipartiteness. The obvious problem that arises is then to ask if there are other complex obstacles to bipartiteness other than and odd cycle.

• First, We assume the graph G = (V,E) is connected
• Next, we pick any node s in V and color it red
• Then we color blue every neighbor of s
• The neighbors of these blue nodes are in turn colored red
• We continue the same process until we have colored the whole graph
• At the end, we either have a valid opposing coloring blue/red of G in which every edge has ends of different coloring, or there is some edge with ends of the same color.If the letter happens, G is not bipartite.

This algorithm thus uses BFS: we are coloring each layer at a times,with consecutive layers having different colors, where odd-numbered layers are colored blue while the even-numbered layers are red.

Thus to implement it, we just use BFS and add an extra array color which will indicate the color of the nodes.
In BFS,

• whenever we are adding a node v to the list L[i+1], we just assign:
  • color[v] = red if i+1 is an even number and
  • color[v] = blue if i+1 is an odd number
• At the end of the algorithm, we just search for an edge whose ends received the same color

• Just like BFS, the algorithm described above takes O(m+n) time.
• If there is no edge of G joining two nodes of the same layer, G is a bipartite graph.
• If there is an edge of G joining two nodes of the same layer, G is not a bipartite graph

Thus BFS algorithm can be used to efficiently test whether or not a graph is bipartite. This answers the problem asking whether or not a given graph is bipartite, and is a very good application of the BFS.

This section was interesting, as it gave us a more direct application of the BFS. I give it a 9/10.