graph coloring Algorithm

Vertex colouring is normally used to introduce graph coloring problems since other colouring problems can be transformed into a vertex colouring case. This is partly pedagogical, and partly because some problems are best study in their non-vertex form, as in the case of edge colouring. The first outcomes about graph colouring deal almost exclusively with planar graphs in the form of the colouring of maps. 

In 1912, George David Birkhoff introduced the chromatic polynomial to study the coloring problems, which was generalized to the Tutte polynomial by Tutte, important structures in algebraic graph theory. While trying to color a map of the counties of England, Francis Guthrie postulated the four color conjecture, note that four colors were sufficient to color the map so that no regions sharing a common border received the same color.
#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 */
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 */
void graphColoring(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)
    {
        printSolution(color);
        return;
    }

    /* 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 */
            graphColoring(graph, m, color, v + 1);

            /* If assigning color c doesn't lead to a solution
               then remove it */
            color[v] = 0;
        }
    }
}

/* A utility function to print solution */
void printSolution(int color[])
{
    printf(" Following are the assigned colors \n");
    for (int i = 0; i < V; i++)
        printf(" %d ", color[i]);
    printf("\n");
}

// driver program to test above function
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

    int color[V];

    for (int i = 0; i < V; i++)
        color[i] = 0;

    graphColoring(graph, m, color, 0);
    return 0;
}

LANGUAGE:

DARK MODE: