The graph coloring (also called as vertex coloring) is a way of coloring the vertices of a graph such that no two adjacent vertices share the same color. In this post we will discuss a greedy algorithm for graph coloring and try to minimize the number of colors used.

For example, consider below graph,

It can be colored in many ways by using minimum 3 colors.

Please note that we can’t color the above graph using 2 colors.

Before discussing greedy algorithm to color graphs, lets talk about basic graph coloring terminology.

*k*-colorable graph –

A coloring using at most *k* colors is called a (proper) ** k-coloring **and graph that can be assigned a (proper)

*k*-coloring is

**.**

*k*-colorable*k*-chromatic graph –

The smallest number of colors needed to color a graph *G* is called its **chromatic number **and a graph that is** k-chromatic** if its chromatic number is exactly

*k.*

It states that a connected graph can be colored with only x colors where x is maximum degree of any vertex in the graph except for complete graphs and graphs containing odd length cycle, which requires x + 1 colors.

**Greedy coloring** *considers the vertices of the graph in sequence and assigns each vertex its first available color*. i.e. vertices are considered in a specific order v_{1}, v_{2}, .. v_{n} and v_{i} is assigned the smallest available color which is not used by any of v_{i}‘s neighbors.

Greedy coloring don’t always use the minimum number of colors possible to color a graph. For a graph of maximum degree x, greedy coloring will use at most x + 1 colors. Greedy coloring can be arbitrarily bad; for example, below crown graph (a complete bipartite graph) having n vertices can be 2-colored (refer left image), but greedy coloring resulted in n/2 colors (refer right image).

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 |
#include <bits/stdc++.h> using namespace std; // Number of vertices in the graph #define N 6 // data structure to store graph edges struct Edge { int src, dest; }; class Graph { public: // A array of vectors to represent adjacency list vector<int> adjList[N]; // Constructor Graph(vector<Edge> edges) { // add edges to the undirected graph for (int i = 0; i < edges.size(); i++) { int src = edges[i].src; int dest = edges[i].dest; adjList[src].push_back(dest); adjList[dest].push_back(src); } } }; // array can handle up to 20 node graph. Add more colors for graphs // containing more than 20 vertices string color[] = {"", "BLUE", "GREEN", "RED", "YELLOW", "ORANGE", "PINK", "BLACK", "BROWN", "WHITE", "PURPLE", "VOILET"}; // assign colors to vertices of graph void colorGraph(Graph const &graph) { // stores color assigned to each vertex map<int, int> result; // assign color to vertex one by one for (int u = 0; u < N; u++) { // set to store color of adjacent vertices of u set<int> assigned; // check colors of adjacent vertices of u and store in set for (int i : graph.adjList[u]) if (result[i]) assigned.insert(result[i]); // check for first free color int color = 1; for (auto c : assigned ) { if (color != c) break; color++; } // assigns vertex u the first available color result[u] = color; } for (int v = 0; v < N; v++) cout << "Color assigned to vertex " << v << " is " << color[result[v]] << endl; } // main function int main() { // vector of graph edges as per above diagram vector<Edge> edges = { {0, 1}, {0, 4}, {0, 5}, {4, 5}, {1, 4}, {1, 3}, {2, 3}, {2, 4}, }; // create a graph from edges Graph graph(edges); // color graph using greedy algorithm colorGraph(graph); return 0; } |

**Output: **

Color assigned to vertex 0 is BLUE

Color assigned to vertex 1 is GREEN

Color assigned to vertex 2 is BLUE

Color assigned to vertex 3 is RED

Color assigned to vertex 4 is RED

Color assigned to vertex 5 is GREEN

**Applications of graph coloring – **

The problem of coloring a graph arises in many practical areas such as pattern matching, designing seating plans, scheduling exam time table, solving Sudoku puzzles, etc.

**References:**

https://en.wikipedia.org/wiki/Greedy_coloring

https://en.wikipedia.org/wiki/Graph_coloring

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply