Question

Given a graph G with no odd cycles, we want to color the vertices with two colors, red and white (go Huskers!) such that no two neighbors have the same color. Give a linear algorithm to accomplish this, analyze its running time, and prove it is correct.

Answer 1

When solving algorithmic question, we should consider each detail of the question as each detail and give us a vital hint. Here the detail is : "The Graph has no odd cycles " which means that the Graph is a Bipartite Graph. And all bipartite graph with more than one vertex can be colored using two colors only. Hence, this condition guarantees that the answer will surely exist.

What is a Bipartite Graph? The vertex set of Graph $\huge V$ can be divided/partitioned into two parts $\huge V_1$ and $\huge V_2$ such that there is no edges among vertices in  $\huge V_1$ and no edges among vertices in $\huge V_2$ . If any edge is present it should be between $\huge V_1$ and $\huge V_2$ . A bipartite graph looks like the following :

А E В D H

The two partitions are $\huge V_1 \{A,B,C,D\}$ and $\huge V_2 \{E,F,G,H\}$ . You can easy color the partition V1 with red color and V2 with the white color.

The actual coloring requires us to traverse the Graph can can be done with a Breadth First Traversal of the Graph.

The below algorithm accomplishes this :

1. Initialize an empty Queue Q.
2. Mark a source vertex as RED and insert into Q.
3. Pop vertex v from Q.
4. Find all unmarked neighbor of v and mark them a different color from v. (This means that if v is RED then mark neighbors as WHITE and vice-versa)
5. Insert all the neighbors in Q.
6. Repeat Steps 3,4,5 till the Q becomes empty.
7. If any vertex remains unmarked then make it source and start from step 2.

Note that the Graph may be disconnected, then step 7 takes care of the Disconnected Graph case.

Time Complexity : This is simply the Breadth First Search with additional constant time steps to mark the vertex and can be done in $\huge O(V+E)$ time. This is because all Vertex will be pushed in Q only once. Also, to check the neighbors we have to look at the E edges. The overall complexity would be $\huge O(V+E)$ .

Proof : We know that a graph is Bipartite if and only if it has no odd cycles. A breadth First Traversal of the Bipartite Graph will lead to the bi-coloring because for every edge traverse we would be jumping from the partition V1 to V2 with one partition being colored as Red and the other as White. This preserves the "no neighbor with the same color" property. Hence, the algorithm is correct.