[Math] How to find all proper colorings (four coloring) of a graph with a brute force algorithm

coloringgraph theory

I'd like to implement a brute force algorithm to search ALL the different colorings of a map.

In terms of graph theory I'd like to find all four colorings of the vertices of a planar graph (the dual representing the map).

I need help or hints to put me on the right direction.

I'm interested in maps in which each face is an opaque rectangle layered on all previous rectangles, overlapping partially. Each consecutive rectangle starts at a consecutive y coordinate. The next picture should better clarify what I mean.

The faces are numbered from 1 to n

  • face 1 is the face on the bottom of the pile
  • face (n-1) is the face at the top
  • face n is the infinite face surrounding all others

For the meaning of different colorings you can refer to this question:

I was thinking to pre-set the colors of faces and use a classical brute force algorithm to get four coloring of the map. I already implemented the brute

force algorithm to find the proper coloring of a map and I can also force the color of faces to find particolar colorings.

The problem is that I'm not coming up with an algorithm to do it automatically and to be sure to find ALL colorings.

To see what I have so far, you can watch this video on youtube:

http://www.youtube.com/watch?v=sP9gnOLpG9w

What I know is that:

  • Since the colors of three neighboor faces can be arbitrary, face number n, face number 1 and the face touching both (face n and face 1), can have these fixed colors: blue, red, green

Manually I found these colorings:

This is a cross site post on cstheory.

Best Answer

You can generate all 4 (or other number) colorings using Sage, an open source computer math system. You can use it free online without having to install it at http://www.sagenb.org/

If you can input your graph in Sage to the symbol G, then the following code will print all the graph G with all the different colorings

for C in sage.graphs.graph_coloring.all_graph_colorings(G, 4):
    G.plot(vertex_colors = C)
Related Question