The vertex colouring problem is to colour the vertices of a graph in such a way that no two adjacent vertices are the same colour. The decision problem of whether a graph can be coloured in m or fewer colours is NP-complete.

Although the problem is intractable, a bactracking algorithm can be used to reduce the number of colourings that need to be tried. The algorithm works by colouring the vertices one at a time, and backtracking if at any point it becomes impossible to colour the next vertex differently from all of its neighbours.

typedef void(*vertex_colouringfn)(const unsigned int *, size_t);

static unsigned int promising(int i, const unsigned int **adjmat, const unsigned int *colours)
{
    int j;
    unsigned int ok = 1;

    for (j = 0; j < i && ok; j++) {
        if (adjmat[i][j] && colours[i] == colours[j]) {
            /* Adjacent vertex is the same colour */
            ok = 0;
        }
    }
    return ok;
}

static void vertex_colouring_recursive(int i, const unsigned int **adjmat, size_t len,
        unsigned int *colours, unsigned int m, vertex_colouringfn fun)
{
    unsigned int colour;

    if (promising(i, adjmat, colours)) {
        if (i == len - 1) {
            /* Coloured every vertex successfully */
            fun(colours, len);
        }
        else if (i < (int)len - 1) {
            /* Try every colour for the next vertex */
            for (colour = 0; colour < m; colour++) {
                colours[i + 1] = colour;
                vertex_colouring_recursive(i + 1, adjmat, len, colours, m, fun);
            }
        }
    }
}

void vertex_colouring(const unsigned int **adjmat, size_t len, unsigned int m, 
        vertex_colouringfn fun)
{
    unsigned int *colours = calloc(len, sizeof(unsigned int));
    if (colours == NULL) {
        return;
    }
    vertex_colouring_recursive(-1, adjmat, len, colours, m, fun);
    free(colours);
}

This is an example program with a small graph and m = 3:

static void print_colouring(const unsigned int *colours, size_t len)
{
    unsigned int i;
    for (i = 0; i < len; i++) {
        printf("%d ", colours[i]);
    }
    printf("\n");
}

int main(void)
{
    unsigned int v0[] = {0, 1, 1, 1, 0};
    unsigned int v1[] = {1, 0, 1, 0, 1};
    unsigned int v2[] = {1, 1, 0, 1, 1};
    unsigned int v3[] = {1, 0, 1, 0, 1};
    unsigned int v4[] = {0, 1, 1, 1, 0};
    const unsigned int *adjmat[] = {v0, v1, v2, v3, v4};
    const size_t len = sizeof(adjmat) / sizeof(unsigned int*);
    const unsigned int m = 3; /* Number of colours */
    vertex_colouring(adjmat, len, m, print_colouring);
    return 0;
}