CODEWITHSUNDEEP
algorithmgraph
BreezeWind
BreezeWind

Reputation: 688

I need an algorithm that will both find the minimal number of colors for coloring a graph and ensure that no two adajcent vertices have the same color

I need a backtracking algorithm for coloring a graph by respecting the fact that no adjacent vertices can have the same color. We're talking about an undirected connected graph. I also need the same algorithm to determine the minimal number of different colors needed to color the graph. This basically implies that I need to find the chromatic number.

I have found how to color the graph with the backtracking method but I haven't found how to find the chromatic number. Is there well known algorithm for this (using backtracking, I already know about a greedy approach).

Upvotes: 0

Views: 384

Answers (1)

Axel Kemper
Axel Kemper

Reputation: 11322

Using the MiniZinc constraint server, you can express such a problem quite easily:

%  Petersen Graph
set of int: Colors = 1..3;
set of int: Nodes = 1..10;
set of int: Edges = 1..15;
array[Edges] of Nodes: aFrom = [ 1, 2, 3, 4, 1, 1, 2, 3, 4,  5, 6,  7, 7,  8, 6 ];
array[Edges] of Nodes: aTo   = [ 2, 3, 4, 5, 5, 6, 7, 8, 9, 10, 8, 10, 9, 10, 9 ];

array[int] of string: colorName = [ "red", "green", "blue", "purple", "yellow", "brown", "black" ];

array[Nodes] of var Colors: nodeColor;

constraint
  forall(e in Edges) (
      nodeColor[aFrom[e]] != nodeColor[aTo[e]]
  );

solve satisfy;

output [ show(colorName[nodeColor[n]]) ++ "\n" | n in Nodes ];

To determine the minimal number of colors, you can decrement Colors until no solution is found.

Upvotes: 0

Related Questions