Graph coloring Algorithm

5
votes

From wiki http://en.wikipedia.org/wiki/Graph_coloring

In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges share the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color.

Given 'n' colors and 'm' vertices, how easily can a graph coloring algorithm be implemented in a programming language?

Language no barrier.

Just a brain teaser.

(Assume Graph and vertex objects exist)

Edit:
After reading wiki , the problem is NP-complete
Time to revisit maths books :)
my bad.
sorry.

Just curious,
Has this been tried ? as in writing programs for same?
I heard that this is used in optical networks?

Isn't this similar to cube coloring??
(minimum number of colors to color faces of cube so that no two sides share the same color?)

4
algorithmcolorsgraph
Do you want to minimize the number or colors? If you need face coloring then the information on the graph itself does not suffice. - Tomaž Pisanski
yes minimizing number of colors . - Amitd
If you need pseudo-code in java. Please check this stackoverflow.com/questions/9020742/… - user1245222

4 Answers

8
votes

It's an NP complete problem, read the Wikipedia entry for more information on various methods of solving.

4
votes

If you are given 2 colors, and the graph is 2-colorable (i.e. it's a bipartite graph), then you can do it in polynomial time quite trivially.

I gave a pseudocode as answer to this question: Graph colouring algorithm: typical scheduling problem.

2
votes

In my Master's Thesis I testing coloring algorithms. The simplest algorithm is Edge Backtrace.

This is my implementation in Java:

public boolean edgeBackTrace (List<Edge<T>> edgesList, Map<Edge<T>, List<Edge<T>>> neighborEdges) {
  for (Edge<T> e : edgesList) {
    e.setColor(0);
  }
  int i = 0;
  while (true){
    Edge<T> edge = edgesList.get(i);
    edge.setColor(edge.getColor() + 1);
    if (edge.getColor().equals(4)) {
      edge.setColor(0);
      if (i == 0) {
        return true;
      } else {
        i--;
      }
    } else {
      boolean diferentColor = false;

      for (Edge<T> e : neighborEdges.get(edge)) {
        if (e.getColor().equals(edge.getColor())) {
          diferentColor = true;
        }
      }

      if (diferentColor == false) {
        i++;
        if (i == edgesList.size()) {
          return false;
        }
      }
    }
  }
}

The algorithm returns a value of true if the graph has coloring. You can see in edgesList as the color, the individual edges.

1
votes

As mentioned, the general problem is np-complete. Bipartite graphs can be colored using only 2 colors.

It is also true that planar graphs (graphs that do not contain K3,3 or K5 as sub graphs, as per Kuratowski's theorem) can be colored with 4 colors.