Graph coloring Algorithm

Question

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

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
– Tomaž Pisanski, Commented Mar 15, 2010 at 6:25
If you need pseudo-code in java. Please check this stackoverflow.com/questions/9020742/… — user1245222
– user1245222, Commented Apr 30, 2012 at 16:41

zellio · Accepted Answer · 2010-03-15 06:11:29Z

9

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

answered Mar 15, 2010 at 6:11

zellio

32.8k1 gold badge46 silver badges64 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Amitd Over a year ago

ahh..my bad .. should have attended math classes more often :) or at least read "wiki" better.

Tomaž Pisanski Over a year ago

Actually, vertex coloring and edge coloring are two problems. Vertex-coloring is NP complete if you fix the number of colors and is NP-hard if you want to minimize the number of colors.

zellio Over a year ago

@ Tomaž Pisanski you are correct - I assumed vertex colouring and he does say "Given 'n' colours and 'm' vertices, " which to me means fixed colours for a given trial

Community · Accepted Answer · 2017-05-23 10:32:33Z

4

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.

edited May 23, 2017 at 10:32

CommunityBot

11 silver badge

answered Mar 15, 2010 at 6:34

polygenelubricants

385k129 gold badges568 silver badges627 bronze badges

Comments

thomas.adamjak · Accepted Answer · 2016-03-07 14:16:11Z

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.

pnt · Accepted Answer · 2010-03-15 23:10:10Z

1

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.

answered Mar 15, 2010 at 23:10

pnt

1,9161 gold badge20 silver badges29 bronze badges

2 Comments

DarthVader Over a year ago

I thought that was map coloring that you can paint every map with at most 4 colors.

pnt Over a year ago

@user177883 Yes, a map is technically a planar graph :)

Collectives™ on Stack Overflow

Graph coloring Algorithm

4 Answers 4

3 Comments

Comments

Comments

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

3 Comments

Comments

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related