Question: Write a short note on Graph coloring
0

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

Marks: 10M

Year: May 2016

ADD COMMENTlink
modified 2.2 years ago  • written 2.2 years ago by gravatar for Barkha Barkha750
1

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

Step1:

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.

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