Graph Coloring Using Greedy Algorithm

We introduced graph coloring and applications in previous post. As discussed in the previous post, graph coloring is widely used. Unfortunately, there is no efficient algorithm available for coloring a graph with minimum number of colors as the problem is a known NP Complete problem. There are approximate algorithms to solve the problem though. Following is the basic Greedy Algorithm to assign colors. It doesn't guarantee to use minimum colors, but it guarantees an upper bound on the number of colors. The basic algorithm never uses more than d+1 colors where d is the maximum degree of a vertex in the given graph.

Graph Coloring Using Greedy Algorithm:

• Color first vertex with first color. 
• Do following for remaining V-1 vertices. 
  • Consider the currently picked vertex and color it with the lowest numbered color that has not been used on any previously colored vertices adjacent to it. If all previously used colors appear on vertices adjacent to v, assign a new color to it.

Below is the implementation of the above Greedy Algorithm.

// A C++ program to implement greedy algorithm for graph coloring #include <iostream> #include <list> using namespace std; // A class that represents an undirected graph class Graph {  int V; // No. of vertices  list<int> *adj; // A dynamic array of adjacency lists public:  // Constructor and destructor  Graph(int V) { this->V = V; adj = new list<int>[V]; }  ~Graph() { delete [] adj; }  // function to add an edge to graph  void addEdge(int v, int w);  // Prints greedy coloring of the vertices  void greedyColoring(); }; void Graph::addEdge(int v, int w) {  adj[v].push_back(w);  adj[w].push_back(v); // Note: the graph is undirected } // Assigns colors (starting from 0) to all vertices and prints // the assignment of colors void Graph::greedyColoring() {  int result[V];  // Assign the first color to first vertex  result[0] = 0;  // Initialize remaining V-1 vertices as unassigned  for (int u = 1; u < V; u++)  result[u] = -1; // no color is assigned to u  // A temporary array to store the available colors. True  // value of available[cr] would mean that the color cr is  // assigned to one of its adjacent vertices  bool available[V];  for (int cr = 0; cr < V; cr++)  available[cr] = false;  // Assign colors to remaining V-1 vertices  for (int u = 1; u < V; u++)  {  // Process all adjacent vertices and flag their colors  // as unavailable  list<int>::iterator i;  for (i = adj[u].begin(); i != adj[u].end(); ++i)  if (result[*i] != -1)  available[result[*i]] = true;  // Find the first available color  int cr;  for (cr = 0; cr < V; cr++)  if (available[cr] == false)  break;  result[u] = cr; // Assign the found color  // Reset the values back to false for the next iteration  for (i = adj[u].begin(); i != adj[u].end(); ++i)  if (result[*i] != -1)  available[result[*i]] = false;  }  // print the result  for (int u = 0; u < V; u++)  cout << "Vertex " << u << " ---> Color "  << result[u] << endl; } // Driver program to test above function int main() {  Graph g1(5);  g1.addEdge(0, 1);  g1.addEdge(0, 2);  g1.addEdge(1, 2);  g1.addEdge(1, 3);  g1.addEdge(2, 3);  g1.addEdge(3, 4);  cout << "Coloring of graph 1 \n";  g1.greedyColoring();  Graph g2(5);  g2.addEdge(0, 1);  g2.addEdge(0, 2);  g2.addEdge(1, 2);  g2.addEdge(1, 4);  g2.addEdge(2, 4);  g2.addEdge(4, 3);  cout << "\nColoring of graph 2 \n";  g2.greedyColoring();  return 0; } 

// A Java program to implement greedy algorithm for graph coloring import java.io.*; import java.util.*; import java.util.LinkedList; // This class represents an undirected graph using adjacency list class Graph {  private int V; // No. of vertices  private LinkedList<Integer> adj[]; //Adjacency List  //Constructor  Graph(int v)  {  V = v;  adj = new LinkedList[v];  for (int i=0; i<v; ++i)  adj[i] = new LinkedList();  }  //Function to add an edge into the graph  void addEdge(int v,int w)  {  adj[v].add(w);  adj[w].add(v); //Graph is undirected  }  // Assigns colors (starting from 0) to all vertices and  // prints the assignment of colors  void greedyColoring()  {  int result[] = new int[V];  // Initialize all vertices as unassigned  Arrays.fill(result, -1);  // Assign the first color to first vertex  result[0] = 0;  // A temporary array to store the available colors. False  // value of available[cr] would mean that the color cr is  // assigned to one of its adjacent vertices  boolean available[] = new boolean[V];    // Initially, all colors are available  Arrays.fill(available, true);  // Assign colors to remaining V-1 vertices  for (int u = 1; u < V; u++)  {  // Process all adjacent vertices and flag their colors  // as unavailable  Iterator<Integer> it = adj[u].iterator() ;  while (it.hasNext())  {  int i = it.next();  if (result[i] != -1)  available[result[i]] = false;  }  // Find the first available color  int cr;  for (cr = 0; cr < V; cr++){  if (available[cr])  break;  }  result[u] = cr; // Assign the found color  // Reset the values back to true for the next iteration  Arrays.fill(available, true);  }  // print the result  for (int u = 0; u < V; u++)  System.out.println("Vertex " + u + " ---> Color "  + result[u]);  }  // Driver method  public static void main(String args[])  {  Graph g1 = new Graph(5);  g1.addEdge(0, 1);  g1.addEdge(0, 2);  g1.addEdge(1, 2);  g1.addEdge(1, 3);  g1.addEdge(2, 3);  g1.addEdge(3, 4);  System.out.println("Coloring of graph 1");  g1.greedyColoring();  System.out.println();  Graph g2 = new Graph(5);  g2.addEdge(0, 1);  g2.addEdge(0, 2);  g2.addEdge(1, 2);  g2.addEdge(1, 4);  g2.addEdge(2, 4);  g2.addEdge(4, 3);  System.out.println("Coloring of graph 2 ");  g2.greedyColoring();  } } // This code is contributed by Aakash Hasija 

# Python3 program to implement greedy  # algorithm for graph coloring  def addEdge(adj, v, w): adj[v].append(w) # Note: the graph is undirected adj[w].append(v) return adj # Assigns colors (starting from 0) to all # vertices and prints the assignment of colors def greedyColoring(adj, V): result = [-1] * V # Assign the first color to first vertex result[0] = 0; # A temporary array to store the available colors.  # True value of available[cr] would mean that the # color cr is assigned to one of its adjacent vertices available = [False] * V # Assign colors to remaining V-1 vertices for u in range(1, V): # Process all adjacent vertices and # flag their colors as unavailable for i in adj[u]: if (result[i] != -1): available[result[i]] = True # Find the first available color cr = 0 while cr < V: if (available[cr] == False): break cr += 1 # Assign the found color result[u] = cr # Reset the values back to false  # for the next iteration for i in adj[u]: if (result[i] != -1): available[result[i]] = False # Print the result for u in range(V): print("Vertex", u, " ---> Color", result[u]) # Driver Code if __name__ == '__main__': g1 = [[] for i in range(5)] g1 = addEdge(g1, 0, 1) g1 = addEdge(g1, 0, 2) g1 = addEdge(g1, 1, 2) g1 = addEdge(g1, 1, 3) g1 = addEdge(g1, 2, 3) g1 = addEdge(g1, 3, 4) print("Coloring of graph 1 ") greedyColoring(g1, 5) g2 = [[] for i in range(5)] g2 = addEdge(g2, 0, 1) g2 = addEdge(g2, 0, 2) g2 = addEdge(g2, 1, 2) g2 = addEdge(g2, 1, 4) g2 = addEdge(g2, 2, 4) g2 = addEdge(g2, 4, 3) print("\nColoring of graph 2") greedyColoring(g2, 5) # This code is contributed by mohit kumar 29 

// A C# program to implement greedy algorithm for graph coloring using System; using System.Collections.Generic; // This class represents an undirected graph using adjacency list class Graph {  private int V; // No. of vertices  private List<int>[] adj; //Adjacency List  //Constructor  public Graph(int v)  {  V = v;  adj = new List<int>[v];  for (int i=0; i<v; ++i)  adj[i] = new List<int>();  }  //Function to add an edge into the graph  public void addEdge(int v,int w)  {  adj[v].Add(w);  adj[w].Add(v); //Graph is undirected  }  // Assigns colors (starting from 0) to all vertices and  // prints the assignment of colors  public void greedyColoring()  {  int[] result = new int[V];  // Initialize all vertices as unassigned  for(int i = 0; i < V; i++)  {  result[i] = -1;  }  // Assign the first color to first vertex  result[0] = 0;  // A temporary array to store the available colors. False  // value of available[cr] would mean that the color cr is  // assigned to one of its adjacent vertices  bool[] available = new bool[V];  // Initially, all colors are available  for(int i = 0; i < V; i++)  {  available[i] = true;  }  // Assign colors to remaining V-1 vertices  for (int u = 1; u < V; u++)  {  // Process all adjacent vertices and flag their colors  // as unavailable  foreach (int i in adj[u])  {  if (result[i] != -1)  available[result[i]] = false;  }  // Find the first available color  int cr;  for (cr = 0; cr < V; cr++)  {  if (available[cr])  break;  }  result[u] = cr; // Assign the found color  // Reset the values back to true for the next iteration  for(int i = 0; i < V; i++)  {  available[i] = true;  }  }  // print the result  for (int u = 0; u < V; u++)  Console.WriteLine("Vertex " + u + " ---> Color " + result[u]);  }  // Driver method  public static void Main(string[] args)  {  Graph g1 = new Graph(5);  g1.addEdge(0, 1);  g1.addEdge(0, 2);  g1.addEdge(1, 2);  g1.addEdge(1, 3);  g1.addEdge(2, 3);  g1.addEdge(3, 4);  Console.WriteLine("Coloring of graph 1");  g1.greedyColoring();  Graph g2 = new Graph(5);  g2.addEdge(0, 1);  g2.addEdge(0, 2);  g2.addEdge(1, 2);  g2.addEdge(1, 4);  g2.addEdge(2, 4);  g2.addEdge(4, 3);  Console.WriteLine("\nColoring of graph 2");  g2.greedyColoring();  } } 

<script> // Javascript program to implement greedy // algorithm for graph coloring // This class represents a directed graph  // using adjacency list representation  class Graph{   // Constructor  constructor(v) {  this.V = v;   this.adj = new Array(v);    for(let i = 0; i < v; ++i)   this.adj[i] = [];    this.Time = 0; } // Function to add an edge into the graph addEdge(v,w) {  this.adj[v].push(w);    // Graph is undirected  this.adj[w].push(v);  } // Assigns colors (starting from 0) to all  // vertices and prints the assignment of colors greedyColoring() {  let result = new Array(this.V);  // Initialize all vertices as unassigned  for(let i = 0; i < this.V; i++)  result[i] = -1;  // Assign the first color to first vertex  result[0] = 0;  // A temporary array to store the available   // colors. False value of available[cr] would  // mean that the color cr is assigned to one   // of its adjacent vertices  let available = new Array(this.V);    // Initially, all colors are available  for(let i = 0; i < this.V; i++)  available[i] = true;  // Assign colors to remaining V-1 vertices  for(let u = 1; u < this.V; u++)  {    // Process all adjacent vertices and   // flag their colors as unavailable  for(let it of this.adj[u])  {  let i = it;  if (result[i] != -1)  available[result[i]] = false;  }  // Find the first available color  let cr;  for(cr = 0; cr < this.V; cr++)  {  if (available[cr])  break;  }    // Assign the found color  result[u] = cr;   // Reset the values back to true  // for the next iteration  for(let i = 0; i < this.V; i++)  available[i] = true;  }  // print the result  for(let u = 0; u < this.V; u++)  document.write("Vertex " + u + " ---> Color " +   result[u] + "<br>"); } }  // Driver code let g1 = new Graph(5); g1.addEdge(0, 1); g1.addEdge(0, 2); g1.addEdge(1, 2); g1.addEdge(1, 3); g1.addEdge(2, 3); g1.addEdge(3, 4); document.write("Coloring of graph 1<br>"); g1.greedyColoring(); document.write("<br>"); let g2 = new Graph(5); g2.addEdge(0, 1); g2.addEdge(0, 2); g2.addEdge(1, 2); g2.addEdge(1, 4); g2.addEdge(2, 4); g2.addEdge(4, 3); document.write("Coloring of graph 2<br> "); g2.greedyColoring(); // This code is contributed by avanitrachhadiya2155 </script> 

Output: 

Coloring of graph 1 Vertex 0 ---> Color 0 Vertex 1 ---> Color 1 Vertex 2 ---> Color 2 Vertex 3 ---> Color 0 Vertex 4 ---> Color 1 Coloring of graph 2 Vertex 0 ---> Color 0 Vertex 1 ---> Color 1 Vertex 2 ---> Color 2 Vertex 3 ---> Color 0 Vertex 4 ---> Color 3 

Time Complexity: O(V^2 + E), in worst case.
Auxiliary Space: O(1), as we are not using any extra space.

Analysis of Graph Coloring Using Greedy Algorithm:

The above algorithm doesn't always use minimum number of colors. Also, the number of colors used sometime depend on the order in which vertices are processed. For example, consider the following two graphs. Note that in graph on right side, vertices 3 and 4 are swapped. If we consider the vertices 0, 1, 2, 3, 4 in left graph, we can color the graph using 3 colors. But if we consider the vertices 0, 1, 2, 3, 4 in right graph, we need 4 colors. 
 

So the order in which the vertices are picked is important. Many people have suggested different ways to find an ordering that work better than the basic algorithm on average. The most common is Welsh–Powell Algorithm which considers vertices in descending order of degrees. 

How does the basic algorithm guarantee an upper bound of d+1? 

Here d is the maximum degree in the given graph. Since d is maximum degree, a vertex cannot be attached to more than d vertices. When we color a vertex, at most d colors could have already been used by its adjacent. To color this vertex, we need to pick the smallest numbered color that is not used by the adjacent vertices. If colors are numbered like 1, 2, ...., then the value of such smallest number must be between 1 to d+1 (Note that d numbers are already picked by adjacent vertices). 
This can also be proved using induction. See this video lecture for proof.