Graph coloring Algorithm

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?)

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

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.

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.

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.