Introduction to Graph Coloring

Graph Coloring refers to the problem of coloring vertices of a graph in such a way that no two adjacent
vertices have the same color. This is also called the vertex coloring problem. If coloring is done using
at most m colors, it is called m-coloring.

Chromatic Number: The chromatic number of G, is the minimal number of colours necessary for
vertex coloring of graph and is denoted by X(G).

X(G) = 1, if G is a Null Graph

X(G) >= 2, if G is not a Null Graph

For example, the following can be colored a minimum of 2 colors and 3 colors.

Defining the Problem

We’re given a graph G consisting of V vertices and E edges connecting them. We’re asked to assign a
colour to each vertex of the graph such that the following conditions are fulfilled:

1. No two adjacent vertices have the same colour. Remember that two vertices are considered
adjacent if an edge connects them.

2. The number of colours used is the minimum possible.

For example, let’s consider the following graph:

As we can see, the graph consists of V = 7 vertices and E = 11 edges connecting them. We numbered
the vertices from 1 to 7 and the colours from 1 to 3. Overall, we used 3 colours to solve the problem.
Note that no adjacent vertices have the same colour. Plus, our solution is the optimal one, as there’s no
way to solve the problem using fewer colours.

Since the problem is considered NP-Complete, no efficient algorithm can solve all types of graphs.
However, we’ll present following Greedy Approache that can give close to optimal solutions. However,
other approaches are also available. For example DSatur Approach (out of syllabus), Backtracking.

Greedy Approach
Let’s discuss the theoretical idea over an example and then jump into the implementation.

Theoretical Idea
In the greedy approach, we find a random ordering for the graph vertices. In addition, we number the
colours starting from 1. Then, we iterate over the vertices individually and assign the feasible colour
with the lowest number to each.

Let’s consider the same graph that we presented before. Assume we use the following vertex ordering:

{1, 2, 3, 4, 5, 6, 7}

Then, we’ll get the following solution:

Solving the problem is done using the following steps:

1. Start with vertex 1 and use the first colour.

2. Vertex 2 doesn’t have any adjacent colours. Thus, we use the first one as well.
3. Vertex 3 has a blue vertex adjacent to it. Thus, we use the second one.
4. Similarly, vertex 4 has a blue vertex adjacent to it twice, so we also use the second one.
5. Vertex 5 has blue and green adjacent to it. Therefore, we have to use the third colour for it.
6. Vertex 6 now has blue, green, and red vertices adjacent to it. As a result, we have to use the new
fourth colour.
7. Finally, vertex 7 has blue, green, and orange adjacents. Since the third colour (red) is not
adjacent, we can use it.
As a result, we used 4 colours to solve the problem with this approach which is not optimal. However,
it’s still close to the actual optimal result.
Implementation
Take a look at the implementation of the greedy approach:

We define a function that takes graph G and the array of vertices V in the order in which to apply the
colouring. We start by defining an array called color filled with zeros, indicating that we initially don’t
have any colour assigned for the vertices.

Then, we iterate over all vertices. For each vertex, we iterate over all its edges and add the child’s
colour to the usedColors set. After that, we move to find the correct colour to assign for the current
vertex.

We start the currentColor with zero and perform multiple iterations to do that. In each iteration, we
increase the currentColor by one and check if it’s not part of the userColors. If so, we assign it to the
current vertex.

Finally, we return the color array containing the solution to our problem.

Time Complexity
Throughout the algorithm, we iterate over each node exactly once. We iterate over all its edges for each
vertex and add the colours to a set. Thus, each edge is checked twice; once from each vertex, it
connects. After that, we iterate over the colours to find the accepted one with the lowest number. Since
each edge can make at most one colour invalid, we’ll perform E steps before finding a valid solution
for the vertex.

Therefore, assuming we use a HashSet with a constant complexity for adding elements, the overall time
complexity will be O(V + E).

M-Coloring Problem
Given an undirected graph and a number m, the task is to color the given graph with at most m colors
such that no two adjacent vertices of the graph are colored with the same color

Note: Here coloring of a graph means the assignment of colors to all vertices

Below is an example of a graph that can be colored with 3 different colors:

M-Coloring Problem using Backtracking

Assign colors one by one to different vertices, starting from vertex 0. Before assigning a color, check
for safety by considering already assigned colors to the adjacent vertices i.e check if the adjacent
vertices have the same color or not. If there is any color assignment that does not violate the conditions,
mark the color assignment as part of the solution. If no assignment of color is possible then backtrack
and return false

Follow the given steps to solve the problem:

1. Create a recursive function that takes the graph, current index, number of vertices, and color
array.
2. If the current index is equal to the number of vertices. Print the color configuration in the color
array.
3. Assign a color to a vertex from the range (1 to m).
4. For every assigned color, check if the configuration is safe, (i.e. check if the adjacent vertices
do not have the same color) and recursively call the function with the next index and number of
vertices otherwise, return false.
5. If any recursive function returns true then return true.
6. If no recursive function returns true then return false
Illustration:
• To color the graph, color each node one by one.
• To color the first node there are 3 choices of colors Red, Green and Blue, so lets take the red
color for first node.
• After Red color for first node is fixed then we have made choice for second node in similar
manner as we did for first node, then for 3rd node and so on.
• There is one important point to remember. while choosing color for the node, it should not be
same as the color of the adjacent node.

• As shown in the above diagram, all the solutions are shown by coloring the first node in Red.
• Let’s choose Green color for the first node and explore the options for the remaining nodes.

• As shown in the above diagram, all the solutions are shown by coloring the first node in Green.
• Let’s choose Blue color for the first node and explore the options for the remaining nodes.
Below is the implementation of the above approach:

// C program for solution of M

// Coloring problem using backtracking

#include <stdbool.h>
#include <stdio.h>

// Number of vertices in the graph

#define V 4

void printSolution(int color[]);

/*
A utility function to check if the current color assignment is safe for vertex v i.e. checks whether the edge exists or not (i.e,
graph[v][i]==1). If exist then checks whether the color to be filled in the new vertex(c is sent in the parameter) is already
used by its adjacent vertices(i-->adj vertices) or not (i.e, color[i]==c)
*/
bool isSafe(int v, bool graph[V][V], int color[], int c)
{
for (int i = 0; i < V; i++)
if (graph[v][i] && c == color[i])
return false;
return true;
}

/* A recursive utility function to solve m coloring problem */

bool graphColoringUtil(bool graph[V][V], int m, int color[],
int v)
{
/* base case: If all vertices are assigned a color then return true */
if (v == V)
return true;

/* Consider this vertex v and try different colors */

 for (int c = 1; c <= m; c++) {
/* Check if assignment of color c to v is fine*/
if (isSafe(v, graph, color, c)) {
color[v] = c;

/* recur to assign colors to rest of the vertices */

if (graphColoringUtil(graph, m, color, v + 1)
== true)
return true;

/* If assigning color c doesn't lead to a solution then remove it */

color[v] = 0;
}
}

/* If no color can be assigned to this vertex then return false */

return false;
}

/*
This function solves the m Coloring problem using Backtracking. It mainly uses graphColoringUtil() to solve the problem.
It returns false if the m colors cannot be assigned, otherwise return true and prints assignments of colors to all vertices.
Please note that there may be more than one solutions, this function prints one of the feasible solutions.
*/
bool graphColoring(bool graph[V][V], int m)
{
// Initialize all color values as 0.
// This initialization is needed.
// correct functioning of isSafe().
int color[V];
for (int i = 0; i < V; i++)
color[i] = 0;

// Call graphColoringUtil() for vertex 0

if (graphColoringUtil(graph, m, color, 0) == false) {
printf("Solution does not exist");
return false;
}

// Print the solution

printSolution(color);
return true;
}

/* A utility function to print solution */

void printSolution(int color[])
{
printf("Solution Exists:"
" Following are the assigned colors \n");
for (int i = 0; i < V; i++)
 printf(" %d ", color[i]);
printf("\n");
}

// Driver code

int main()
{
/*
Create following graph and test whether it is 3 colorable
(3)-------(2)
| / |
| / |
| / |
(0)-------(1)
*/
bool graph[V][V] = {
{ 0, 1, 1, 1 },
{ 1, 0, 1, 0 },
{ 1, 1, 0, 1 },
{ 1, 0, 1, 0 },
};
int m = 3; // Number of colors

// Function call
graphColoring(graph, m);
return 0;
}

Greedy-Coloring
C programming language implementation of Greedy Coloring, a graph theory algorithm.

In the study of graph coloring problems in mathematics and computer science, a greedy coloring is a
coloring of the vertices of a graph formed by a greedy algorithm that considers the vertices of the graph
in sequence and assigns each vertex its first available color. Greedy colorings can be found in linear
time, but they do not in general use the minimum number of colors possible.

#include<stdio.h>
typedef struct interval
{
int num,start,end,degree,color;
int* Edges;
}Interval;
void GreedyColoring();
void addEdge(Interval, Interval);
int partition(Interval *, int, int);
void quick_sort(Interval *, int, int);
void swap(Interval*, Interval*);

void main()
{
GreedyColoring();
}

void GreedyColoring()
{
int i,j, amount,last=1, MaxDegree=0, MinDegree = 0,Edges=0, Chrom=1;
printf("Please input amount:\n");
scanf_s("%d", &amount);
Interval* list = (Interval*)malloc(amount * sizeof(Interval));
printf("Please enter %d intervals (start - end)\n", amount);
for (i = 0; i < amount; i++)//Fill the list
{
list[i].num = i;
scanf_s("%d", &((list + i)->start));
scanf_s("%d", &((list + i)->end));
list[i].degree = 0;
list[i].Edges = (int*)calloc(amount, sizeof(int));
list[i].color = 1;

}
printf("The intervals family is:\n");
for (i = 0; i < amount; i++)//Prints the intervals family
{
printf("[%d , %d]", (list + i)->start, (list + i)->end);
if (i != amount - 1)
printf(" , ");
}
quick_sort(list, 0, amount-1);//Order list by start time (ascending)
printf("\nOrdered by start list:\n");
for (i = 0; i < amount; i++)//Prints the intervals family
{
printf("[%d , %d]", (list + i)->start, (list + i)->end);
if (i != amount - 1)
printf(" , ");
}

//----------------------------------------------------------
for (i = 0; i < amount; i++)//coloring loop
{
last = 1;
 for (j = 0; j < i; j++)
{
if (((list[i].end) < (list[j].start)) || (list[j].end < list[i].start))
{
continue;
}
else
{
addEdge(list[i], list[j]);
Edges++;
list[i].degree++;
list[j].degree++;
last++;
if (list[i].color == list[j].color)
list[i].color = last;
}
}
}
for (i = 0; i < amount; i++)
{
if (list[i].degree <= MinDegree)
MinDegree = list[i].degree;
if (list[i].degree >= MaxDegree)
MaxDegree = list[i].degree;
if (list[i].color >= Chrom)
Chrom = list[i].color;
}
//----------------------------------------------------
printf("\nG Edges: %d\nChromatic Number Of G:%d\nMax Degree: %d\nMin Degree: %d\nG
Complement Edges: %d\nMax Degree Of G Complement: %d\nMin Degree Of G Complement: %d\
n",Edges,Chrom,MaxDegree,MinDegree,(amount*(amount-1)/2)-Edges,amount-1-MinDegree,amount-
1-MaxDegree);
for (i = 0; i < amount; i++)
{
printf("\n [%d,%d]:", list[i].start,list[i].end);
printf(" degree :%d", list[i].degree);
printf(" color :'%d'", list[i].color);
printf("\n[");
for (j = 0; j < amount; j++)
{
printf("%d ", list[i].Edges[j]);
}
printf("]\n");
free(list[i].Edges);
}
printf("Optional coloring:\n");
for (j = 1; j <= Chrom; j++)
{
printf("Color '%d' : ", j);
 printf("{");
for (i = 0; i < amount; i++)
{
if (list[i].color == j)
printf("[%d , %d]", (list + i)->start, (list + i)->end);
}
printf("}");
printf("\n");
}
free(list);
}

void addEdge(Interval u, Interval v)

{
if ((u.Edges[v.num]) == 0 && (v.Edges[u.num] == 0))
{
u.Edges[v.num] = 1;
v.Edges[u.num] = 1;
}
}

void swap(Interval* a, Interval* b)

{
Interval temp;
temp = *a;
*a = *b;
*b = temp;
}

int partition(Interval *family, int left, int right)

{
int first = left;
Interval pivot = family[first];
int pos;
while (left < right)
{
while (family[right].start > pivot.start) right--;
while ((left < right) && (family[left].start <= pivot.start)) left++;
if (left < right)
swap(family + left, family + right);
}
pos = right;
family[first] = family[pos];
family[pos] = pivot;
return pos;
}
void quick_sort(Interval *family, int first, int last)
{
int pos;
if (first < last)
{
pos = partition(family, first, last);
quick_sort(family, first, pos - 1);
quick_sort(family, pos + 1, last);
}
}