**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-

Vertex | a | b | c | d | e | f |

Color | C1 | C2 | C1 | C2 | C1 | C2 |

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-

Vertex | a | b | c | d | e | f |

Color | C1 | C2 | C2 | C3 | C3 | C1 |

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-

Vertex | a | b | c | d | e | f | g |

Color | C1 | C2 | C1 | C3 | C2 | C3 | C4 |

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-

Vertex | a | b | c | d | e | f |

Color | C1 | C2 | C3 | C1 | C2 | C3 |

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**.