I need an algorithm to get the chromatic number of a graph.

Question

Given the adjacency matrix of a graph, I need to obtain the chromatic number (minimum number of colours needed to paint every node of a graph so that adjacent nodes get different colours).

Preferably it should be a java algorithm, and I don't care about performance.

Thanks.

Edit: recently introduced a fix so the answer is more accurately. now it will recheck his position with his previous positions.

Now a new question comes up. Which will be better to raise his 'number-color'? the node in which i am standing, or the node i am visiting (asking if i am adjacent to it)?

public class Modelacion {

public static void main(String args[]) throws IOException{

//  given the matrix ... which i have hidden the initialization here

    int[][] matriz = new int[40][40];

    int color[] = new int[40];

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

    Cromatico c = new Cromatico(matriz, color);

}

}

import java.io.IOException;

public class Cromatico {

Cromatico(int[][]matriz, int[] color, int fila) throws IOException{

    for (int i = 0; i<fila;i++){
        for (int j = 0 ; j<fila;j++){
            if (matriz[i][j] == 1 && color[i] == color [j]){
                if (j<i)
                    color [i] ++;
                else
                    color [j] ++;
            }
        }
    }

    int numeroCromatico = 1;
    for (int k = 0; k<fila;k++){
        System.out.print(".");
        numeroCromatico = Math.max(numeroCromatico, color[k]);  
    }

    System.out.println();
    System.out.println("el numero cromatico del grafo es: " + numeroCromatico);

}

}

Answer 1

Super slow, but it should work:

int chromaticNumber(Graph g) {
  for (int ncolors = 1; true; ncolors++) {
    if (canColor(g, ncolors)) return ncolors;
  }
}

boolean canColor(Graph g, int ncolors) {
  return canColorRemaining(g, ncolors, 0));
}

// recursive routine - the first colors_so_far nodes have been colored,
// check if there is a coloring for the rest.
boolean canColorRemaining(Graph g, int ncolors, int colors_so_far) {
  if (colors_so_far == g.nodes()) return true;
  for (int c = 0; c < ncolors; c++) {
    boolean ok = true;
    for (int v : g.adjacent(colors_so_far)) {
      if (v < colors_so_far && g.getColor(v) == c) ok = false;
    }
    if (ok) {
      g.setColor(colors_so_far, c);
      if (canColorRemaining(g, ncolors, colors_so_far + 1)) return true;
    }
  }
  return false;
}

Answer 2

Finding the chromatic number of a graph is NP-Complete (see Graph Coloring). It is NP-Complete even to determine if a given graph is 3-colorable (and also to find a coloring).

The wiki page linked to in the previous paragraph has some algorithms descriptions which you can probably use.

btw, since it is NP-Complete and you don't really care about performance, why don't you try using brute force?

Guess a chromatic number k, try all possibilities of vertex colouring (max k^n possibilities), if it is not colorable, new guess for chromatic number = min{n,2k}. If it is k-colorable, new guess for chromatic number = max{k/2,1}. Repeat, following the pattern used by binary search and find the optimal k.

Good luck!

And to answer your edit.

Neither option of incrementing the color will work. Also, your algorithm is O(n^2). That itself is enough to tell it is highly likely that your algorithm is wrong, even without looking for counterexamples. This problem is NP-Complete!