# Graph coloring

Graph coloring is a fundamental problem in graph theory where the goal is to assign colors to the vertices of a graph such that no two adjacent vertices share the same color. This article provides an in-depth explanation of the graph coloring problem and presents a C code implementation of the Backtracking Algorithm to solve it.

## Problem Statement

Given an undirected graph, the task is to color its vertices in such a way that no two adjacent vertices have the same color while using the minimum number of colors.

## Description with Example

Imagine you have a map of countries with borders representing the edges of a graph. The graph coloring problem can be likened to coloring the map such that no two adjacent countries share the same color, and you want to use the least number of colors possible.

## Idea to Solve

The Backtracking Algorithm is a common approach to solving the graph coloring problem. It starts by assigning colors to vertices one by one, backtracking whenever it finds a conflict (two adjacent vertices with the same color), and exploring different color options.

## Pseudocode

``````function graphColor(graph, max_color):
initialize color array with 0
if fillColor(graph, color, max_color, 1, 0):
print "Graph Color"
for each vertex v:
print "Node [v]->color [color[v]]"
else:
print "Given colors [max_color] are not enough"

function fillColor(graph, color, max_color, node_color, node):
if node_color > max_color:
return false
if node == N:
return true
if color[node] == 0:
for each color_option from 1 to max_color:
if isSafe(graph, color, color_option, node):
color[node] = color_option
if fillColor(graph, color, max_color, 1, node + 1):
return true
color[node] = 0
return false

function isSafe(graph, color, node_color, node):
return false
return true``````

## Algorithm Explanation

1. Initialize the `color` array to keep track of colors assigned to vertices.
2. Call the `fillColor` function, which iterates through each vertex and tries to assign a color.
3. Inside the `fillColor` function: a. If the current node_color exceeds max_color, return false. b. If all vertices are colored, return true. c. If the current vertex has not been colored:
• Iterate through color options from 1 to max_color.
• If a color_option is safe for the current vertex (no adjacent vertex has the same color):
• Assign the color_option to the current vertex.
• Recursively call `fillColor` for the next vertex.
• If successful, return true. Otherwise, backtrack by resetting color[node]. d. Return false if no color_option is suitable for the current vertex.

## Program Solution

``````// C program
// Graph coloring
#include <stdio.h>

// Define size of adjacency matrix
#define N 6

// Sets the default color of each vertex in graph
void defult_color(int color[N])
{
for (int i = 0; i < N; ++i)
{
color[i] = 0;
}
}
// This function is assigning node color,
// And check adjacent node color are valid or not
int fill_color(int graph[N][N], int color[N], int max_color, int node_color, int node)
{
if (node_color > max_color)
{
return 0;
}
if (node == N)
{
//When color are vaild
return 1;
}
if (color[node] == 0)
{
//When need to set color
int status = 1;
//Check neighbors
for (int i = 0; i < N && status == 1; ++i)
{
if (graph[node][i] == 1 && color[i] == node_color)
{
// When need to change color
if (fill_color(graph, color, max_color, node_color + 1, node))
{
return 1;
}
else
{
status = 0;
}
}
}
if (status == 1)
{
//When color is valid to node
color[node] = node_color;

//Visit to next node
if (fill_color(graph, color, max_color, 1, node + 1))
{
return 1;
}
//reset node color
color[node] = 0;
}
}
return 0;
}
// Handles the request of find given graph node color
void graph_color(int graph[N][N], int max_color)
{
if (max_color <= 0)
{
return;
}
// This are used to store vertex color
int color[N];
defult_color(color);
if (fill_color(graph, color, max_color, 1, 0))
{
//When given color are suitable
printf("\n Graph Color");
for (int i = 0; i < N; ++i)
{
//Display node color
printf("\n Node [%d]->color [%d]", i, color[i]);
}
}
else
{
//In case if, given color are not suitable to fill all adjacent vertices.
// (violation of color) Then
printf("\n Given colors [%d] are not enough\n", max_color);
}
}
int main()
{
//Define node relation in adjacency matrix
int graph[N][N] = {
{
0 , 1 , 0 , 1 , 0 , 1
} ,
{
1 , 0 , 1 , 0 , 1 , 0
} ,
{
0 , 1 , 0 , 1 , 1 , 1
} ,
{
1 , 0 , 1 , 0 , 1 , 0
} ,
{
0 , 1 , 1 , 1 , 0 , 1
} ,
{
1 , 0 , 1 , 0 , 1 , 0
} , };
//Define number of possible color
int max_color = 3;
graph_color(graph, max_color);
return 0;
}``````

#### Output

`````` Graph Color
Node ->color 
Node ->color 
Node ->color 
Node ->color 
Node ->color 
Node ->color ``````
``````/*
Java program
Graph coloring
*/
class MyGraph
{
// Sets the default color of each vertex in graph
public void defult_color(int[] color,int size)
{
for (int i = 0; i < size; ++i)
{
color[i] = 0;
}
}
// This function is assigning node color,
// And check adjacent node color are valid or not
public boolean fill_color(int [][]graph, int[] color, int max_color, int node_color, int node,int size)
{
if (node_color > max_color)
{
return false;
}
if (node == size)
{
//When color are vaild
return true;
}
if (color[node] == 0)
{
//When need to set color
boolean status = true;
//Check neighbors
for (int i = 0; i < size && status == true; ++i)
{
if (graph[node][i] == 1 && color[i] == node_color)
{
// When need to change color
if (fill_color(graph, color, max_color, node_color + 1, node, size))
{
return true;
}
else
{
status = false;
}
}
}
if (status == true)
{
//When color is valid to node
color[node] = node_color;
//Visit to next node
if (fill_color(graph, color, max_color, 1, node + 1,size))
{
return true;
}
//reset node color
color[node] = 0;
}
}
return false;
}
// Handles the request of find given graph node color
public void graph_color(int[][] graph, int max_color,int size)
{
if (max_color <= 0)
{
return;
}

// This are used to store vertex color
int[] color = new int[size];

defult_color(color,size);

if (fill_color(graph, color, max_color, 1, 0,size))
{
//When given color are suitable
System.out.print("\n Graph Color");
for (int i = 0; i < size; ++i)
{
//Display node color
System.out.print("\n Node [" + i + "]->color [" + color[i] + "]");
}
}
else
{
//In case if, given color are not suitable to fill all adjacent vertices.
// (violation of color) Then
System.out.print("\n Given colors [" + max_color + "] are not enough\n");
}
}
public static void main(String[] args)
{
MyGraph obj = new MyGraph();

//Define node relation in adjacency matrix
int [][] graph =
{
{
0 , 1 , 0 , 1 , 0 , 1
} ,
{
1 , 0 , 1 , 0 , 1 , 0
} ,
{
0 , 1 , 0 , 1 , 1 , 1
} ,
{
1 , 0 , 1 , 0 , 1 , 0
} ,
{
0 , 1 , 1 , 1 , 0 , 1
} ,
{
1 , 0 , 1 , 0 , 1 , 0
} ,
};

// Get size of adjacency matrix
int size = graph.length;

//Define number of possible color
int max_color = 3;

//Test
obj.graph_color(graph, max_color,size);
}
}``````

#### Output

`````` Graph Color
Node ->color 
Node ->color 
Node ->color 
Node ->color 
Node ->color 
Node ->color ``````
``````//Include header file
#include <iostream>
#define N 6
using namespace std;
/*
C++ program
Graph coloring
*/
class MyGraph
{
public:
// Sets the default color of each vertex in graph
void defult_color(int color[], int size)
{
for (int i = 0; i < size; ++i)
{
color[i] = 0;
}
}
// This function is assigning node color,
// And check adjacent node color are valid or not
bool fill_color(int graph[N][N], int color[], int max_color, int node_color, int node, int size)
{
if (node_color > max_color)
{
return false;
}
if (node == size)
{
//When color are vaild
return true;
}
if (color[node] == 0)
{
//When need to set color
bool status = true;
//Check neighbors
for (int i = 0; i < size && status == true; ++i)
{
if (graph[node][i] == 1 && color[i] == node_color)
{
// When need to change color
if (this->fill_color(graph, color, max_color, node_color + 1, node, size))
{
return true;
}
else
{
status = false;
}
}
}
if (status == true)
{
//When color is valid to node
color[node] = node_color;
//Visit to next node
if (this->fill_color(graph, color, max_color, 1, node + 1, size))
{
return true;
}
//reset node color
color[node] = 0;
}
}
return false;
}
// Handles the request of find given graph node color
void graph_color(int graph[N][N], int max_color, int size)
{
if (max_color <= 0)
{
return;
}
// This are used to store vertex color
int color[size];
this->defult_color(color, size);
if (this->fill_color(graph, color, max_color, 1, 0, size))
{
//When given color are suitable
cout << "\n Graph Color";
for (int i = 0; i < size; ++i)
{
//Display node color
cout << "\n Node [" << i << "] -> color [" << color[i] << "]";
}
}
else
{
//In case if, given color are not suitable to fill all adjacent vertices.
// (violation of color) Then
cout << "\n Given colors [" << max_color << "] are not enough\n";
}
}
};
int main()
{
MyGraph obj = MyGraph();
//Define node relation in adjacency matrix
int graph[N][N] = {
{
0 , 1 , 0 , 1 , 0 , 1
} , {
1 , 0 , 1 , 0 , 1 , 0
} , {
0 , 1 , 0 , 1 , 1 , 1
} , {
1 , 0 , 1 , 0 , 1 , 0
} , {
0 , 1 , 1 , 1 , 0 , 1
} , {
1 , 0 , 1 , 0 , 1 , 0
} };
// Get size of adjacency matrix
int size = N;
//Define number of possible color
int max_color = 3;
//Test
obj.graph_color(graph, max_color, size);
return 0;
}``````

#### Output

`````` Graph Color
Node  -> color 
Node  -> color 
Node  -> color 
Node  -> color 
Node  -> color 
Node  -> color ``````
``````//Include namespace system
using System;
/*
C# program
Graph coloring
*/
class MyGraph
{
// Sets the default color of each vertex in graph
public void defult_color(int[] color, int size)
{
for (int i = 0; i < size; ++i)
{
color[i] = 0;
}
}
// This function is assigning node color,
// And check adjacent node color are valid or not
public Boolean fill_color(int[,] graph, int[] color, int max_color, int node_color, int node, int size)
{
if (node_color > max_color)
{
return false;
}
if (node == size)
{
//When color are vaild
return true;
}
if (color[node] == 0)
{
//When need to set color
Boolean status = true;
//Check neighbors
for (int i = 0; i < size && status == true; ++i)
{
if (graph[node,i] == 1 && color[i] == node_color)
{
// When need to change color
if (fill_color(graph, color, max_color, node_color + 1, node, size))
{
return true;
}
else
{
status = false;
}
}
}
if (status == true)
{
//When color is valid to node
color[node] = node_color;
//Visit to next node
if (fill_color(graph, color, max_color, 1, node + 1, size))
{
return true;
}
//reset node color
color[node] = 0;
}
}
return false;
}
// Handles the request of find given graph node color
public void graph_color(int[,] graph, int max_color, int size)
{
if (max_color <= 0)
{
return;
}
// This are used to store vertex color
int[] color = new int[size];
defult_color(color, size);
if (fill_color(graph, color, max_color, 1, 0, size))
{
//When given color are suitable
Console.Write("\n Graph Color");
for (int i = 0; i < size; ++i)
{
//Display node color
Console.Write("\n Node [" + i + "] -> color [" + color[i] + "]");
}
}
else
{
//In case if, given color are not suitable to fill all adjacent vertices.
// (violation of color) Then
Console.Write("\n Given colors [" + max_color + "] are not enough\n");
}
}
public static void Main(String[] args)
{
MyGraph obj = new MyGraph();
//Define node relation in adjacency matrix
int[,] graph = {
{
0 , 1 , 0 , 1 , 0 , 1
} , {
1 , 0 , 1 , 0 , 1 , 0
} , {
0 , 1 , 0 , 1 , 1 , 1
} , {
1 , 0 , 1 , 0 , 1 , 0
} , {
0 , 1 , 1 , 1 , 0 , 1
} , {
1 , 0 , 1 , 0 , 1 , 0
}
};
// Get size of adjacency matrix
int size = graph.GetLength(0);
//Define number of possible color
int max_color = 3;
//Test
obj.graph_color(graph, max_color, size);
}
}``````

#### Output

`````` Graph Color
Node  -> color 
Node  -> color 
Node  -> color 
Node  -> color 
Node  -> color 
Node  -> color ``````
``````<?php
/*
Php program
Graph coloring
*/

class MyGraph
{
// This function is assigning node color,
// And check adjacent node color are valid or not
public	function fill_color( & \$graph, & \$color, \$max_color, \$node_color, \$node, \$size)
{
if (\$node_color > \$max_color)
{
return false;
}
if (\$node == \$size)
{
//When color are vaild
return true;
}
if (\$color[\$node] == 0)
{
//When need to set color
\$status = true;
//Check neighbors
for (\$i = 0; \$i < \$size && \$status == true; ++\$i)
{
if (\$graph[\$node][\$i] == 1 && \$color[\$i] == \$node_color)
{
// When need to change color
if (\$this->fill_color(\$graph, \$color, \$max_color, \$node_color + 1, \$node, \$size))
{
return true;
}
else
{
\$status = false;
}
}
}
if (\$status == true)
{
//When color is valid to node
\$color[\$node] = \$node_color;
//Visit to next node
if (\$this->fill_color(\$graph, \$color, \$max_color, 1, \$node + 1, \$size))
{
return true;
}
//reset node color
\$color[\$node] = 0;
}
}
return false;
}
// Handles the request of find given graph node color
public	function graph_color( & \$graph, \$max_color, \$size)
{
if (\$max_color <= 0)
{
return;
}
// This are used to store vertex color
\$color = array_fill(0, \$size, 0);
if (\$this->fill_color(\$graph, \$color, \$max_color, 1, 0, \$size))
{
//When given color are suitable
echo "\n Graph Color";
for (\$i = 0; \$i < \$size; ++\$i)
{
//Display node color
echo "\n Node [". \$i ."] -> color [". \$color[\$i] ."]";
}
}
else
{
//In case if, given color are not suitable to fill all adjacent vertices.
// (violation of color) Then
echo "\n Given colors [". \$max_color ."] are not enough\n";
}
}
}

function main()
{
\$obj = new MyGraph();
//Define node relation in adjacency matrix
\$graph = array(array(0, 1, 0, 1, 0, 1), array(1, 0, 1, 0, 1, 0), array(0, 1, 0, 1, 1, 1), array(1, 0, 1, 0, 1, 0), array(0, 1, 1, 1, 0, 1), array(1, 0, 1, 0, 1, 0));
// Get size of adjacency matrix
\$size = count(\$graph);
//Define number of possible color
\$max_color = 3;
//Test
\$obj->graph_color(\$graph, \$max_color, \$size);
}
main();``````

#### Output

`````` Graph Color
Node  -> color 
Node  -> color 
Node  -> color 
Node  -> color 
Node  -> color 
Node  -> color ``````
``````/*
Node Js program
Graph coloring
*/

class MyGraph
{
// This function is assigning node color,
// And check adjacent node color are valid or not
fill_color(graph, color, max_color, node_color, node, size)
{
if (node_color > max_color)
{
return false;
}
if (node == size)
{
//When color are vaild
return true;
}
if (color[node] == 0)
{
//When need to set color
var status = true;
//Check neighbors
for (var i = 0; i < size && status == true; ++i)
{
if (graph[node][i] == 1 && color[i] == node_color)
{
// When need to change color
if (this.fill_color(graph, color, max_color, node_color + 1, node, size))
{
return true;
}
else
{
status = false;
}
}
}
if (status == true)
{
//When color is valid to node
color[node] = node_color;
//Visit to next node
if (this.fill_color(graph, color, max_color, 1, node + 1, size))
{
return true;
}
//reset node color
color[node] = 0;
}
}
return false;
}
// Handles the request of find given graph node color
graph_color(graph, max_color, size)
{
if (max_color <= 0)
{
return;
}
// This are used to store vertex color
var color = Array(size).fill(0);
if (this.fill_color(graph, color, max_color, 1, 0, size))
{
//When given color are suitable
process.stdout.write("\n Graph Color");
for (var i = 0; i < size; ++i)
{
//Display node color
process.stdout.write("\n Node [" + i + "] -> color [" + color[i] + "]");
}
}
else
{
//In case if, given color are not suitable to fill all adjacent vertices.
// (violation of color) Then
process.stdout.write("\n Given colors [" + max_color + "] are not enough\n");
}
}
}

function main()
{
var obj = new MyGraph();
//Define node relation in adjacency matrix
var graph = [
[0, 1, 0, 1, 0, 1],
[1, 0, 1, 0, 1, 0],
[0, 1, 0, 1, 1, 1],
[1, 0, 1, 0, 1, 0],
[0, 1, 1, 1, 0, 1],
[1, 0, 1, 0, 1, 0]
];
// Get size of adjacency matrix
var size = graph.length;
//Define number of possible color
var max_color = 3;
//Test
obj.graph_color(graph, max_color, size);
}
main();``````

#### Output

`````` Graph Color
Node  -> color 
Node  -> color 
Node  -> color 
Node  -> color 
Node  -> color 
Node  -> color ``````
``````#   Python 3 program
#   Graph coloring

class MyGraph :
#  This function is assigning node color,
#  And check adjacent node color are valid or not
def fill_color(self, graph, color, max_color, node_color, node, size) :
if (node_color > max_color) :
return False

if (node == size) :
# When color are vaild
return True

if (color[node] == 0) :
# When need to set color
status = True
# Check neighbors
i = 0
while (i < size and status == True) :
if (graph[node][i] == 1 and color[i] == node_color) :
#  When need to change color
if (self.fill_color(graph, color, max_color, node_color + 1, node, size)) :
return True
else :
status = False

i += 1

if (status == True) :
# When color is valid to node
color[node] = node_color
# Visit to next node
if (self.fill_color(graph, color, max_color, 1, node + 1, size)) :
return True

# reset node color
color[node] = 0

return False

#  Handles the request of find given graph node color
def graph_color(self, graph, max_color, size) :
if (max_color <= 0) :
return

#  This are used to store vertex color
color =  * (size)
if (self.fill_color(graph, color, max_color, 1, 0, size)) :
# When given color are suitable
print("\n Graph Color", end = "")
i = 0
while (i < size) :
# Display node color
print("\n Node [", i ,"] -> color [", color[i] ,"]", end = "")
i += 1

else :
# In case if, given color are not suitable to fill all adjacent vertices.
#  (violation of color) Then
print("\n Given colors [", max_color ,"] are not enough\n", end = "")

def main() :
obj = MyGraph()
# Define node relation in adjacency matrix
graph = [
[0, 1, 0, 1, 0, 1],
[1, 0, 1, 0, 1, 0],
[0, 1, 0, 1, 1, 1],
[1, 0, 1, 0, 1, 0],
[0, 1, 1, 1, 0, 1],
[1, 0, 1, 0, 1, 0]
]
#  Get size of adjacency matrix
size = len(graph)
# Define number of possible color
max_color = 3
# Test
obj.graph_color(graph, max_color, size)

if __name__ == "__main__": main()``````

#### Output

`````` Graph Color
Node [ 0 ] -> color [ 1 ]
Node [ 1 ] -> color [ 2 ]
Node [ 2 ] -> color [ 1 ]
Node [ 3 ] -> color [ 2 ]
Node [ 4 ] -> color [ 3 ]
Node [ 5 ] -> color [ 2 ]``````
``````#   Ruby program
#   Graph coloring

class MyGraph
#  This function is assigning node color,
#  And check adjacent node color are valid or not
def fill_color(graph, color, max_color, node_color, node, size)
if (node_color > max_color)
return false
end

if (node == size)
# When color are vaild
return true
end

if (color[node] == 0)
# When need to set color
status = true
# Check neighbors
i = 0
while (i < size && status == true)
if (graph[node][i] == 1 && color[i] == node_color)
#  When need to change color
if (self.fill_color(graph, color, max_color, node_color + 1, node, size))
return true
else
status = false
end

end

i += 1
end

if (status == true)
# When color is valid to node
color[node] = node_color
# Visit to next node
if (self.fill_color(graph, color, max_color, 1, node + 1, size))
return true
end

# reset node color
color[node] = 0
end

end

return false
end

#  Handles the request of find given graph node color
def graph_color(graph, max_color, size)
if (max_color <= 0)
return
end

#  This are used to store vertex color
color = Array.new(size) {0}
if (self.fill_color(graph, color, max_color, 1, 0, size))
# When given color are suitable
print("\n Graph Color")
i = 0
while (i < size)
# Display node color
print("\n Node [", i ,"] -> color [", color[i] ,"]")
i += 1
end

else
# In case if, given color are not suitable to fill all adjacent vertices.
#  (violation of color) Then
print("\n Given colors [", max_color ,"] are not enough\n")
end

end

end

def main()
obj = MyGraph.new()
# Define node relation in adjacency matrix
graph = [
[0, 1, 0, 1, 0, 1],
[1, 0, 1, 0, 1, 0],
[0, 1, 0, 1, 1, 1],
[1, 0, 1, 0, 1, 0],
[0, 1, 1, 1, 0, 1],
[1, 0, 1, 0, 1, 0]
]
#  Get size of adjacency matrix
size = graph.length
# Define number of possible color
max_color = 3
# Test
obj.graph_color(graph, max_color, size)
end

main()``````

#### Output

`````` Graph Color
Node  -> color 
Node  -> color 
Node  -> color 
Node  -> color 
Node  -> color 
Node  -> color ``````
``````/*
Scala program
Graph coloring
*/

class MyGraph
{
// This function is assigning node color,
// And check adjacent node color are valid or not
def fill_color(graph: Array[Array[Int]], color: Array[Int], max_color: Int, node_color: Int, node: Int, size: Int): Boolean = {
if (node_color > max_color)
{
return false;
}
if (node == size)
{
//When color are vaild
return true;
}
if (color(node) == 0)
{
//When need to set color
var status: Boolean = true;
//Check neighbors
var i: Int = 0;
while (i < size && status == true)
{
if (graph(node)(i) == 1 && color(i) == node_color)
{
// When need to change color
if (fill_color(graph, color, max_color, node_color + 1, node, size))
{
return true;
}
else
{
status = false;
}
}
i += 1;
}
if (status == true)
{
//When color is valid to node
color(node) = node_color;
//Visit to next node
if (fill_color(graph, color, max_color, 1, node + 1, size))
{
return true;
}
//reset node color
color(node) = 0;
}
}
return false;
}
// Handles the request of find given graph node color
def graph_color(graph: Array[Array[Int]], max_color: Int, size: Int): Unit = {
if (max_color <= 0)
{
return;
}
// This are used to store vertex color
var color: Array[Int] = Array.fill[Int](size)(0);
if (fill_color(graph, color, max_color, 1, 0, size))
{
//When given color are suitable
print("\n Graph Color");
var i: Int = 0;
while (i < size)
{
//Display node color
print("\n Node [" + i + "] -> color [" + color(i) + "]");
i += 1;
}
}
else
{
//In case if, given color are not suitable to fill all adjacent vertices.
// (violation of color) Then
print("\n Given colors [" + max_color + "] are not enough\n");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: MyGraph = new MyGraph();
//Define node relation in adjacency matrix
var graph: Array[Array[Int]] = Array(Array(0, 1, 0, 1, 0, 1), Array(1, 0, 1, 0, 1, 0), Array(0, 1, 0, 1, 1, 1), Array(1, 0, 1, 0, 1, 0), Array(0, 1, 1, 1, 0, 1), Array(1, 0, 1, 0, 1, 0));
// Get size of adjacency matrix
var size: Int = graph.length;
//Define number of possible color
var max_color: Int = 3;
//Test
obj.graph_color(graph, max_color, size);
}
}``````

#### Output

`````` Graph Color
Node  -> color 
Node  -> color 
Node  -> color 
Node  -> color 
Node  -> color 
Node  -> color ``````
``````/*
Swift 4 program
Graph coloring
*/

class MyGraph
{
// This function is assigning node color,
// And check adjacent node color are valid or not
func fill_color(_ graph: [[Int]],
_ color: inout[Int],
_ max_color: Int,
_ node_color: Int,
_ node: Int,
_ size: Int) -> Bool
{
if (node_color > max_color)
{
return false;
}
if (node == size)
{
//When color are vaild
return true;
}
if (color[node] == 0)
{
//When need to set color
var status: Bool = true;
//Check neighbors
var i: Int = 0;
while (i < size && status == true)
{
if (graph[node][i] == 1 && color[i] == node_color)
{
// When need to change color
if (self.fill_color(graph, &color, max_color, node_color + 1, node, size))
{
return true;
}
else
{
status = false;
}
}
i += 1;
}
if (status == true)
{
//When color is valid to node
color[node] = node_color;
//Visit to next node
if (self.fill_color(graph, &color, max_color, 1, node + 1, size))
{
return true;
}
//reset node color
color[node] = 0;
}
}
return false;
}
// Handles the request of find given graph node color
func graph_color(_ graph: [[Int]], _ max_color: Int, _ size: Int)
{
if (max_color <= 0)
{
return;
}
// This are used to store vertex color
var color: [Int] = Array(repeating: 0, count: size);
if (self.fill_color(graph, &color, max_color, 1, 0, size))
{
//When given color are suitable
print("\n Graph Color", terminator: "");
var i: Int = 0;
while (i < size)
{
//Display node color
print("\n Node [", i ,"] -> color [", color[i],"]", terminator: "");
i += 1;
}
}
else
{
//In case if, given color are not suitable to fill all adjacent vertices.
// (violation of color) Then
print("\n Given colors [", max_color ,"]are not enough\n", terminator: "");
}
}
}
func main()
{
let obj: MyGraph = MyGraph();
//Define node relation in adjacency matrix
let graph: [[Int]] = [[0, 1, 0, 1, 0, 1],
[1, 0, 1, 0, 1, 0],
[0, 1, 0, 1, 1, 1],
[1, 0, 1, 0, 1, 0],
[0, 1, 1, 1, 0, 1],
[1, 0, 1, 0, 1, 0]];
// Get size of adjacency matrix
let size: Int = graph.count;
//Define number of possible color
let max_color: Int = 3;
//Test
obj.graph_color(graph, max_color, size);
}
main();``````

#### Output

`````` Graph Color
Node [ 0 ] -> color [ 1 ]
Node [ 1 ] -> color [ 2 ]
Node [ 2 ] -> color [ 1 ]
Node [ 3 ] -> color [ 2 ]
Node [ 4 ] -> color [ 3 ]
Node [ 5 ] -> color [ 2 ]``````

## Output Explanation

The output demonstrates the successful coloring of the graph's vertices using the Backtracking Algorithm. Each line indicates the color assigned to a vertex. If the given colors are not sufficient to color the graph without conflicts, a message is printed indicating the insufficiency of colors.

## Time Complexity

The time complexity of the Backtracking Algorithm for graph coloring depends on the branching factor (max_color) and the number of vertices (N) in the graph. In the worst case, the algorithm explores all possible color combinations for each vertex, resulting in an exponential time complexity of O(max_color^N).

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.