Graph Coloring Algorithm

Question

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

In its simplest form, this is a way of coloring the vertices of a graph so that two adjacent vertices do not share the same color; this is called vertex coloration. Similarly, a coloring edge assigns a color to each edge so that there are no two adjacent edges of the same color, and a flat color face color assigns a color to each face or region so that none of the two sides that share the border have the same color.

Given the “n” colors and the “m” vertices, how easy can the graph coloring be implemented in a programming language?

Language without a barrier.

Just a brain teaser.

(Assume Graph and vertex objects exist)

Edit:
After reading the wiki, the NP-complete problem.
Time to review the math books :)
my bad.
excuse me.

Just curious.
Have you tried this? how to write programs for the same?
I heard that it is used in optical networks?

Doesn't that look like a cube coloring?
(the minimum number of colors for the colored faces of the cube so that the two sides do not have the same color?)

Answer 1

This is a complete NP problem; read the Wikipedia entry for more information on various solution methods.

Answer 2

2 , 2- (.. ), .

: : .

Answer 3

. - Edge Backtrace.

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

true, . List , .

Answer 4

, np-. .

It is also true that planar graphs (graphs that do not contain K3,3 or K5 as subgraphs, according to Kuratovsky’s theorem) can be colored 4 colors.