4
$\begingroup$

I'm working on an algorithm to colour a map drawn in an editor using 4 colours, as a visual demonstration of the four colour theorem. However, my (imperfect) algorithm was able to colour all maps except this one, which after giving it a go myself I struggled to do. I was also unable to collapse it into an 'untangled' graph, so it's possible there's some illegality about it I've not fully understood (or I'm just bad at graph theory). I'd appreciate any help with solving this, and if possible an explanation of/link to a good algorithm to go about solving problems of this style.

Here's the map:

The map

$\endgroup$
5
  • $\begingroup$ It is similar to this post. $\endgroup$
    – Dietrich Burde
    Jun 1, 2019 at 18:12
  • $\begingroup$ @DietrichBurde If you mean that as in that the graphs are similar for both, could you please write an answer explaining that? I'm pretty weak at graph theory, so I can't figure that out myself (despite trying (and failing)) $\endgroup$
    – Geza Kerecsenyi
    Jun 1, 2019 at 18:14
  • 1
    $\begingroup$ It would be helpful if you described your algorithm. I think this is a nice contrast to the other question, because it is asking for how to color (i.e. method) rather than just asking for a coloring. $\endgroup$
    – xxxxxxxxx
    Jun 1, 2019 at 18:26
  • 1
    $\begingroup$ @Rahul You can use backtracking search. It may run in worst-case exponential time, but it's not very complicated. $\endgroup$
    – Fabio Somenzi
    Jun 1, 2019 at 18:49
  • $\begingroup$ @Fabio: Oh you're right. Hopefully it's still safe to say efficient algorithms are very complicated. $\endgroup$
    – user856
    Jun 1, 2019 at 19:34

3 Answers 3

Reset to default
24
$\begingroup$

4 colored map

This is a possible coloring. Done by hand, either really lucky or not that difficult. Perhaps it'll help with debug of the algorithm and shows that this map is definitely legal.

$\endgroup$
5
  • 4
    $\begingroup$ I also got a (different) coloring by hand within a minute. Why the downvote? $\endgroup$
    – Fabio Somenzi
    Jun 1, 2019 at 18:27
  • 12
    $\begingroup$ Note that the exterior is also a region, which can obviously be colored blue. $\endgroup$
    – Paul Sinclair
    Jun 2, 2019 at 3:46
  • $\begingroup$ "shows that this map is definitely legal" The four-colour theorem already tells us that there's no such thing as an "illegal" map. $\endgroup$
    – David Richerby
    Jun 2, 2019 at 10:56
  • 2
    $\begingroup$ @FabioSomenzi The downvote isn't mine but, to me, the question seems to be "How does one go about 4-colouring planar graphs?" not "Here's a planar graph: please give me a 4-colouring." $\endgroup$
    – David Richerby
    Jun 2, 2019 at 10:58
  • 2
    $\begingroup$ @DavidRicherby "after giving it a go myself I struggled to do. I was also unable to collapse it into an 'untangled' graph, so it's possible there's some illegality" $\endgroup$
    – Fabio Somenzi
    Jun 2, 2019 at 15:13
16
$\begingroup$

The map you have given can be simplified considerably by deleting some of the regions. If you have a region which is adjacent to $1, 2$ or $3$ other regions, you can simply delete it, or amalgamate it into some adjoining region, because when you colour the rest and put the region back, there will be a colour you can use.

The map you have looks complicated, but I can spot five regions you can simply delete in this example. And once you have deleted those you can possibly iterate the process.

That gives a rather simpler map to colour.

$\endgroup$
12
  • 2
    $\begingroup$ Thanks for the explanation! I've marked you as answer, as upon knowing this, I was able to essentially half the time complexity of my algorithm. $\endgroup$
    – Geza Kerecsenyi
    Jun 1, 2019 at 18:54
  • 2
    $\begingroup$ You can also remove 4-sided regions by removing the borders on two opposite sides, while leaving the two other sides alone. After coloring the resulting graph, you put the borders back in, and change the color in the interior. Since the colors neighboring those two borders are the same, the region is surrounded by at most three colors, and can be given the fourth. (Alas, if a similar trick worked for five-sided regions, the 4 color theorem would be easy to prove,) $\endgroup$
    – Paul Sinclair
    Jun 2, 2019 at 3:53
  • $\begingroup$ @PaulSinclair: That doesn't work. If a region has four neighbors, it's true that at least two must share a color, but the border removal you propose commits to coloring a specific pair the same color. This commitment may commit to a pair that doesn't work out. $\endgroup$
    – user2357112
    Jun 2, 2019 at 5:05
  • $\begingroup$ @user2357112 Paul's method does in fact work, provided you can colour the smaller map. The four colour theorem says you can do this. $\endgroup$
    – Mark Bennet
    Jun 2, 2019 at 6:05
  • 1
    $\begingroup$ @MarkBennet: After thinking it over some more, I've concluded that it mostly works, except if the neighbors you merge were already connected, in which case you have to merge the other pair. This is trivial to check, but does have to be checked. $\endgroup$
    – user2357112
    Jun 2, 2019 at 6:35
1
$\begingroup$

One possible algorithm would be the following:

  1. Take the map, and turn it into a graph.
  2. Delete all nodes with degree $<4$.
  3. Turn the graph into a clause set (a special form of a logical formula) by doing the following:
    a. For every edge $A\to B$ (where, $A,B$ are vertices of the graph), we add the formula $\lnot \left((A_0\Leftrightarrow B_0) \land(A_1\Leftrightarrow B_1) \right)$ as a clause into the clause set.
  4. We run DPLL (or the simpler version, Davis-Putnam) on this clause set.
  5. DPLL will give us a satisfying model. The color (whereas our colors are $0,1,2,3$) of a node $A$ is given by our model as $A= A_0 + 2\cdot A_1$
  6. Determine for every deleted node a possible coloring using the model.

The underlying idea is the following:
Every border in the map says as much as "the bordering areas mustn't be equal" (in terms of color).

By letting our colors be $0,1,2,3$, we can represent each color in binary as $2^0\cdot z_0 + 2^1 \cdot z_1$.
As two numbers are equal iff all their bits are equal, we get for every border in the map between two areas $A,B$ the logic formula: $$\lnot \left((A_0\Leftrightarrow B_0) \land(A_1\Leftrightarrow B_1) \right)$$

Now a 4-coloring is a coloring where this formula holds for exactly every border.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .