Question: Write a short note on Graph coloring

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

Marks: 10M

Year: May 2016

modified 2.5 years ago  • written 2.5 years ago by gravatar for Barkha Barkha750

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 –

enter image description here


enter image description here

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:

enter image description here

Step 3:

enter image description here

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

enter image description here

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

written 2.5 years ago by gravatar for Barkha Barkha750
Please log in to add an answer.