Graph Coloring Algorithm | How to find Chromatic Number

Greedy Coloring Algorithm-

 

Before you go through this article, make sure that you have gone through the previous article on Graph Coloring and Chromatic Number which gives a basic introduction to Graph Coloring and Chromatic Number.

 

  • There is no efficient algorithm known for coloring a graph with minimum number of colors.
  • Graph coloring problem is a NP complete problem.

 

Greedy Algorithm to find chromatic Number of a Graph-

 

Step-01:

Color first vertex with first color.

 

Step-02:

Now, consider the remaining (V-1) vertices one by one and do the following-

 

  • Color the currently picked vertex with the lowest numbered color if it has not been used to color any of the vertices adjacent to it. If it has been used, then choose the next least numbered color.
  • If all the previously used colors have been used to color the vertices adjacent to the currently picked vertex, then assign a new color to the currently picked vertex.

 

Drawbacks of Greedy Algorithm-

 

  • The above algorithm does not always use minimum number of colors.
  • The number of colors used sometimes depend on the order in which the vertices are processed.

 

PRACTICE PROBLEMS BASED ON FINDING THE CHROMATIC NUMBER OF GRAPHS-

 

Problem-01:

Find the chromatic number of the graph shown below-

 

 

Solution-

 

Applying Greedy Algorithm, we have-

 

Vertexabcdef
ColorC1C2C1C2C1C2

 

Thus,

Chromatic Number of the given graph = 2

 

 

Problem-02:

Find the chromatic number of the graph shown below-

 

 

Solution-

 

Applying Greedy Algorithm, we have-

 

Vertexabcdef
ColorC1C2C2C3C3C1

 

Thus,

Chromatic Number of the given graph = 3

 

 

Problem-03:

Find the chromatic number of the graph shown below-

 

 

Solution-

 

Applying Greedy Algorithm, we have-

 

Vertexabcde fg
ColorC1C2C1C3C2C3C4

 

Thus,

Chromatic Number of the given graph = 4

 

 

Problem-04:

Find the chromatic number of the graph shown below-

 

 

Solution-

 

Applying Greedy Algorithm, we have-

 

Vertexabcdef
ColorC1C2C3C1C2C3

 

Thus,

Chromatic Number of the given graph = 3

 

 

Problem-05:

Find the chromatic number of the graph shown below-

 

 

Solution-

 

Applying Greedy Algorithm, we get-

Chromatic Number of the given graph = 3

 

 

 

Get more notes and other study material of Graph Theory.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Summary
Graph Coloring Algorithm | How to find Chromatic Number
Article Name
Graph Coloring Algorithm | How to find Chromatic Number
Description
There is no efficient graph coloring algorithm known for coloring a graph with minimum number of colors. Graph Coloring is a NP Complete Problem. Greedy Algorithm for graph coloring is an algorithm used to properly color the graph. Practice Problems based on finding chromatic number of a graph.
Author
Publisher Name
Gate Vidyalay
Publisher Logo
Liked this article? Share it with your friends and classmates now-