How to Find Chromatic Number | Graph Coloring Algorithm

Chromatic Number-

 

Before you go through this article, make sure that you have gone through the previous article on Chromatic Number.

 

We gave discussed-

  • Graph Coloring is a process of assigning colors to the vertices of a graph.
  • It ensures that no two adjacent vertices of the graph are colored with the same color.
  • Chromatic Number is the minimum number of colors required to properly color any graph.

 

In this article, we will discuss how to find Chromatic Number of any graph.

 

Graph Coloring Algorithm-

 

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

 

However, a following greedy algorithm is known for finding the chromatic number of any given graph.

 

Greedy Algorithm-

 

Step-01:

 

Color first vertex with the 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 its adjacent vertices.
  • If it has been used, then choose the next least numbered color.
  • If all the previously used colors have been used, then assign a new color to the currently picked vertex.

 

Drawbacks of Greedy Algorithm-

 

There are following drawbacks of the above 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.

 

Also Read- Types of Graphs in Graph Theory

 

PRACTICE PROBLEMS BASED ON FINDING CHROMATIC NUMBER OF A GRAPH-

 

Problem-01:

 

Find chromatic number of the following graph-

 

 

Solution-

 

Applying Greedy Algorithm, we have-

 

Vertexabcdef
ColorC1C2C1C2C1C2

 

From here,

  • Minimum number of colors used to color the given graph are 2.
  • Therefore, Chromatic Number of the given graph = 2.

 

The given graph may be properly colored using 2 colors as shown below-

 

 

Problem-02:

 

Find chromatic number of the following graph-

 

 

Solution-

 

Applying Greedy Algorithm, we have-

 

Vertexabcdef
ColorC1C2C2C3C3C1

 

From here,

  • Minimum number of colors used to color the given graph are 3.
  • Therefore, Chromatic Number of the given graph = 3.

 

The given graph may be properly colored using 3 colors as shown below-

 

 

Problem-03:

 

Find chromatic number of the following graph-

 

 

Solution-

 

Applying Greedy Algorithm, we have-

 

Vertexabcde fg
ColorC1C2C1C3C2C3C4

 

From here,

  • Minimum number of colors used to color the given graph are 4.
  • Therefore, Chromatic Number of the given graph = 4.

 

The given graph may be properly colored using 4 colors as shown below-

 

 

Problem-04:

 

Find chromatic number of the following graph-

 

 

Solution-

 

Applying Greedy Algorithm, we have-

 

Vertexabcdef
ColorC1C2C3C1C2C3

 

From here,

  • Minimum number of colors used to color the given graph are 3.
  • Therefore, Chromatic Number of the given graph = 3.

 

The given graph may be properly colored using 3 colors as shown below-

 

 

Problem-05:

 

Find chromatic number of the following graph-

 

 

Solution-

 

Applying Greedy Algorithm,

  • Minimum number of colors required to color the given graph are 3.
  • Therefore, Chromatic Number of the given graph = 3.

 

The given graph may be properly colored using 3 colors as shown below-

 

 

To gain better understanding about How to Find Chromatic Number,

Watch this Video Lecture

 

Get more notes and other study material of Graph Theory.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Summary
How to Find Chromatic Number | Graph Coloring Algorithm
Article Name
How to Find Chromatic Number | Graph Coloring Algorithm
Description
Graph Coloring Algorithm- A Greedy Algorithm exists for Graph Coloring.How to find Chromatic Number of a graph- We follow the Greedy Algorithm to find Chromatic Number of the Graph. Problems on finding Chromatic Number of a given graph.
Author
Publisher Name
Gate Vidyalay
Publisher Logo
Liked this article? Share it with your friends and classmates now-