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; }