Skip to main content

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):
    for each adjacent_vertex to node:
        if color[adjacent_vertex] == node_color:
            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 [0]->color [1]
 Node [1]->color [2]
 Node [2]->color [1]
 Node [3]->color [2]
 Node [4]->color [3]
 Node [5]->color [2]
/*
  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 [0]->color [1]
 Node [1]->color [2]
 Node [2]->color [1]
 Node [3]->color [2]
 Node [4]->color [3]
 Node [5]->color [2]
//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 [0] -> color [1]
 Node [1] -> color [2]
 Node [2] -> color [1]
 Node [3] -> color [2]
 Node [4] -> color [3]
 Node [5] -> color [2]
//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 [0] -> color [1]
 Node [1] -> color [2]
 Node [2] -> color [1]
 Node [3] -> color [2]
 Node [4] -> color [3]
 Node [5] -> color [2]
<?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 [0] -> color [1]
 Node [1] -> color [2]
 Node [2] -> color [1]
 Node [3] -> color [2]
 Node [4] -> color [3]
 Node [5] -> color [2]
/*
  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 [0] -> color [1]
 Node [1] -> color [2]
 Node [2] -> color [1]
 Node [3] -> color [2]
 Node [4] -> color [3]
 Node [5] -> color [2]
#   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 = [0] * (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 [0] -> color [1]
 Node [1] -> color [2]
 Node [2] -> color [1]
 Node [3] -> color [2]
 Node [4] -> color [3]
 Node [5] -> color [2]
/*
  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 [0] -> color [1]
 Node [1] -> color [2]
 Node [2] -> color [1]
 Node [3] -> color [2]
 Node [4] -> color [3]
 Node [5] -> color [2]
/*
  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.

New Comment