Can anybody color this map using the four color theorem?

Question

I thought this was an interesting concept so I tried to make an impossible map using this. I also tested it on a solving website and it ended up giving me 6 different colors...A picture of it

The website's attempt to solve it

Answer 1

Here is one way to do it. I don't know how many variations can exist.

edit : Reasoning for why this is the only one (up to isomorphism) :

The middle layer of three must be three distinct colors, the surrounding must be the fourth color. As we have determined four necessary colors we can without loss of generality assume the colors we have assigned {white,red,yellow,green}. What remains is to determine the inner 7 areas.

The leftmost 4 of these 7 must be in the set {yellow, green} The rightmost 4 must be in the set {red, green}

This locks the middle one to be green. And now the remaining will become systematically determined like a double set of dominoes or a recursion if you will.

Answer 2

Machines are powerful, but humans are apparently better (joke) !

Here is my solution.

EDIT : I think an interesting method would be to color the area that has the most neighbors and then color each area by elimination. Using the chess vocabulary, it is enough to analyze the situation with a depth of $2$, that is to say, to see what happens the next move if I put this particular color, etc...

Answer 3

Adrien I writes "Machines are powerful but humans are apparently better!"

Really?? For graph coloring??

Here's the graph coloring found in 0.000435 seconds by Mathematica:

where the vertices represent regions and edges represent "touching" in the figure.

---

Code:

    g = Graph[{a \[UndirectedEdge] b, a \[UndirectedEdge] c, 
   a \[UndirectedEdge] d, a \[UndirectedEdge] e, 
   a \[UndirectedEdge] f, a \[UndirectedEdge] g, 
   a \[UndirectedEdge] h, a \[UndirectedEdge] i, a \[UndirectedEdge] j,
   b \[UndirectedEdge] c, b \[UndirectedEdge] d, 
   b \[UndirectedEdge] f, b \[UndirectedEdge] g, 
   c \[UndirectedEdge] g, c \[UndirectedEdge] h, 
   c \[UndirectedEdge] i, c \[UndirectedEdge] j,
   d \[UndirectedEdge] e, e \[UndirectedEdge] f, 
   f \[UndirectedEdge] g, g \[UndirectedEdge] h, 
   h \[UndirectedEdge] i, i \[UndirectedEdge] j}];

myColors = FindVertexColoring[g, {Red, Blue, Yellow, Green}];

gg = Annotate[g,
  VertexStyle -> Thread[VertexList[g] -> myColors]];

Graph[gg, VertexSize -> Large]