Mumbai University > Computer Engineering > Sem 4 > Analysis of Algorithm

Marks: 10M

Year: May 2016

Graph coloring is a problem of coloring each vertex in graph in such a way that no two adjacent vertices have same color and yet m-colors are used. This problem is also called m-coloring problem. If the degree of given graph is d then we can color it with d + 1 colors. The least number of colors needed to color the graph is called its chromatic number.

For example : Consider a graph given in Fig. below. As given in Fig. we require three colors to color the graph. Hence the chromatic number of given graph is 3. We can use backtracking technique to solve the graph coloring problem as follows –

Step1:

A graph G consists of vertices from A to F. There are colors used Red, Green and Blue. We will number then out. That means 1 indicates Red, 2 indicates Green and 3 indicates Blue color.

Step 2:

Step 3:

Thus the graph coloring problem is solved. The state-space tree can be drawn for better understanding of graph coloring technique using backtracking approach-

Here we have assumed, color index Red=1, Green=2 and Blue=3.