We have discussed some basic applications of Graph Traversal and now’s it time to learn some new Graph concepts i.e ** Algorithm of graph coloring**.

In this post, we are going to discuss the algorithm of Graph Coloring and some problems based on it. So, let’s start.

Table of Contents

**What is Graph Coloring ..?**

**Graph coloring** is a method to color the graph with different colors such that no two adjacent nodes have the same color.

For example,

Now we have to color the Graph such that no two **neighboring vertexes** have the same color.

This way we can color the Graph. **NOTE** minimum color required to color the Graph is** 3** but we can color it with more colors as well.

The minimum color required to color a Graph is called its **Chromatic Number**.

**Applications of Graph Coloring**

**Scheduling** : Graph Coloring is useful in scheduling problems since once person can be assigned to one job for particular time slot so, here Graph Coloring helps us.

For example, during examinations too some papers of different departments are common so two schedule them such that every student from every department can get a particular slot for it. Here also Graph Coloring comes to play.**Geographical Maps **: To manage traffics Graph coloring is helpful.**Pattern Matching** : The problem of coloring a graph arises in many practical areas such as designing seating plans and solving Sudoku puzzles.

These are some of the applications now let’s discuss some problems based on it in Graph.

**Leetcode 785: Is Graph Bipartite**

Given an undirected `graph`

, return `true`

if and only if it is bipartite.

Recall that a graph is *bipartite* if we can split it’s set of nodes into two independent subsets A and B such that every edge in the graph has one node in A and another node in B.

The graph is given in the following form: `graph[i]`

is a list of indexes `j`

for which the edge between nodes `i`

and `j`

exists. Each node is an integer between `0`

and `graph.length - 1`

. There are no self edges or parallel edges: `graph[i]`

does not contain `i`

, and it doesn’t contain any element twice.

Example 1:Input:[[1,3], [0,2], [1,3], [0,2]]Output:trueExplanation:The graph looks like this: 0----1 | | | | 3----2 We can divide the vertices into two groups: {0, 2} and {1, 3}.Example 2:Input:[[1,2,3], [0,2], [0,1,3], [0,2]]Output:falseExplanation:The graph looks like this: 0----1 | \ | | \ | 3----2 We cannot find a way to divide the set of nodes into two independent subsets.

**Note** :

`graph`

will have a length in the range [1, 100].- graph[i] will contain integers in the range [0, graph.length – 1].
- graph[i] will not contain or duplicate values.
- The graph is undirected: if any element
`j`

is in`graph[i]`

, then`i`

will be in`graph[j]`

.

**Analysis of Problem Statement**

In the above problem, we have to find if the given graph is **Bipartite **or not.

Before that, let’s understand **what is a Bipartite Graph..**?

**Bipartite Graph**

A **Bipartite Graph** is a graph whose vertices can be divided into two **disjoint sets** so that every edge connects two vertices from different sets. In simple words, there are no edges which connect vertices from the same set, both sets are independent.

Let’s understand it by an example,

Above Graph is a Bipartite Graph as we can divide vertices of the above Graph into two disjoint set.

NOTE no edge connect vertices to two same set and that’s how the above Graph is a Bipartite Graph.

Let’s see another example,

Find out whether above Graph is Bipartite or not and comment it below.

Hope Problem Statement is clear, we just have to find whether a Graph is Bipartite or not.

**Approach to the Problem**

There are many approaches to this problem but we will solve it via **Graph Coloring** and it is the easiest way to solve it.

So, let see the approach.

If you observe carefully, Bipartite Graph can be colored by at most **two colors** and it’s obvious because vertex of every edge belongs to different sets, so we always have the option to color one vertex with one color and other with different color.

And if any Graph cannot be colored with at most two colors then, that Graph is not **Bipartite**.

This is the main logic of our approach, so we just have to check whether Graph needs more than two colors for coloring or not.

### How to check whether a Graph is two colorable or not ..?

For this **DFS Traversal** will help us, we will do a DFS Traversal and check whether coloring the neighbors of the current vertex is possible with one color or not.

If it’s possible then we will move ahead or else we will return false.

Let’s look at the Algorithm,

**Algorithm for Bipartite Graph**

It will be simple **DFS** Traversal only extra part is that we will maintain a **color[]** array.

Initially we will color the first vertex with random color, let’s say **Red**.

Now, while visiting the neighbors, we will check if color of current vertex. If color is **‘Red’**, then we will color it’s neighbors with color ‘**Blue’**.

We will continue the above process for every vertex and if we find that coloring is not possible with only two colors then we will simply return false as the Graph is not **Bipartite**.

Let’s see the code,

```
bool dfs(vector<vector<int>>& graph, int *color, int col, bool *vis, int s)
{
vis[s] =true;
color[s] = col;
for(int i = 0; i < graph[s].size(); i++)
{
if(vis[graph[s][i]] == false && col == 1)
{
if(dfs(graph, color, 2, vis, graph[s][i]) == false)
{
return false;
}
}
else if(vis[graph[s][i]] == false && col == 2)
{
if(dfs(graph, color, 1, vis, graph[s][i]) == false) {
return false;
}
}
else if(color[graph[s][i]] == col) return false;
}
return true;
}
bool isBipartite(vector<vector<int>>& graph) {
int n = graph.size();
int *color = new int[n];
bool *vis = new bool[n];
for(int i = 0; i < n; i++){
color[i] = -1;
vis[i] = false;
}
for(int i = 0; i < n; i++)
{
if(vis[i] == false)
{
if(dfs(graph, color, 1, vis, i) == false) return false;
}
}
return true;
}
```

In the above code, **col = 1** represent ‘Red’ and **col = 2** represent blue.

Please observe the conditions in the **dfs() **function. If current color is 1, then we color neighbors with **color 2** and vice versa.

If we find that color of current node and neighbor node is same then, it is sure that Graph cannot be a bipartite Graph.

Hope code and logic behind Coloring of Graph is clear to you. We will continue with Graph in the next post as well.

Hope you understand the Algorithm for Graph Coloring

That’s all folks..!!!

More Problems : Possible Bipartition