In this tutorial we shall learn about 2 Color Graph Problem
In general graph coloring or edge coloring problem we need to assign color to vertices in such a way that no edge link two vertices with the same color.
Consider the below set of images:
Here graph a is valid. But graph b is invalid because, there is an edge between vertex “b” and vertex “c” that have the same color.
How to solve this?
A simple solution will be to set each vertex with different color. But, the goal is to use few colors as possible.
Graph coloring algorithms are used in many areas, including scheduling application.
Now coming to our topic of 2 color graph problem. What is the need to study this problem now?
In the previous section we learnt about bipartite graph. For a graph to be bipartite it should be a 2 color graph. Hence if we can prove that a graph can be colored by only 2 colors, then that graph is a bipartite graph.
So how to color a graph by using only 2 colors?
It’s simple. Choose a starting vertex, and give it a color say “red”.
Now make all it’s neighbor have other color say “green”.
And all the neighboring vertex of the “green” color vertex, color it “red”.
Continue till al the vertex are colored.
The image below shows step by step procedure for 2 color graph problem.
In the above image, we have colored the graph using only 2 colors.
So to check if the graph is bipartite, we check if the graph is 2 colorable and also it should not contain odd cycle.
Further Reading: