In this new version of the software you can manually color the edges of a map with three colors (RGB) and apply Kempe coloring switch on a Kempe edge chain (path or loop) (http://en.wikipedia.org/wiki/Kempe_chain).
In the new version of the software, isomorphic graphs are automatically removed while processing. This way the generation of all graphs/maps is a lot faster … not as plantri but faster than before.
Download it from here: https://github.com/stefanutti/maps-coloring-java
Using it, I generated all simplified graphs, in graphml format, up to 18 faces:
Here is the video on YouTube:
After having posted the question on mathoverflow, the answer arrived in a blink of an eye.
Here is the answer from Gordon Royle:
Use Gunnar Brinkmann (University of Ghent) and Brendan McKay (Australian National University)’s program “plantri” …
You will discover that there are:
and then going to Sloane’s online encylopaedia you discover: https://oeis.org/A081621
So in short, the answer to your question is “yes, the sequence is fairly well known”.
From plantri http://cs.anu.edu.au/~bdm/plantri:
3-connected planar triangulations with minimum degree 5 (plantri -m5), and 3-connected planar graphs (convex polytopes) with minimum degree 5 (plantri -pm5).
plantri -pm5uv 12
plantri -pm5uv 13
…
. nv ne nf | Number of graphs 12 30 20 | 1 13 33 22 | 0 14 36 24 | 1 15 39 26 | 1 16 42 28 | 3 17 45 30 | 4 18 48 32 | 12 19 51 34 | 23 20 54 36 | 73 21 57 38 | 192 22 60 40 | 651 23 63 42 | 2070 24 66 44 | 7290 25 69 46 | 25381 26 72 48 | 91441 27 75 50 | 329824 28 78 52 | 1204737 29 81 54 | 4412031 30 84 56 | 16248772 31 87 58 | 59995535 32 90 60 | 222231424 33 93 62 | 825028656 34 96 64 | 3069993552 35 99 66 | 11446245342 36 102 68 | 42758608761 37 105 70 | 160012226334 38 108 72 | 599822851579 39 111 74 | 2252137171764 40 114 76 | 8469193859271
Analyzing all 3-regular graphs that have only faces with 5 edges or more (simplified), I empirically found (using a computer program) that many hypothetically possible graphs, that by Euler’s identity may exist (F5=12+F7+2F8+3F9+…), do not actually exist. Using a VF2 algorithm to filter out isomorphic maps, I also noticed that not so many graphs as I expected existed. And that one general category of graphs, that always represents a simplified 3-regular graph, is that of Fullerenes (with 12 faces F5 and an arbitrary number of F6). Here is a list of what I found, so far, for each class of graphs, from 12 faces to 20 faces (surrounding area included).
The question is: Since the computation of maps with 17, 18, 19, 20 faces (simplified and not containing isomorphic graphs) it is taking me very long time (days of CPU time on a PC), is this sequence already known?
I did post this question on: math.stackexchange.com
Many fullerenes are here: http://hog.grinvin.org/Fullerenes.
Last things implemented in the Java program (github):
Here are the maps … four colored … up to 16 faces (ocean included):
 12 |
 14 |
 15 |
 16 |
 16 |
 16 |
And the same graphs elaborated using yWorks:
 12 |
 14 |
 15 |
 16 |
 16 |
 16 |
😦
Too many more things to do and little time:
Bye
And here is the video that shows how to get a Tait colored map (graph) from a rectangular map.
From Wikipedia: “The four color theorem, on vertex coloring of planar graphs, is equivalent to the statement that every bridgeless 3-regular planar graph is of class one (Tait 1880). This statement is now known to be true, due to the proof of the four color theorem by Appel & Haken (1976).”
Here is a simple implementation of this equivalence, that converts a map from “4-face-colored” to “3-edge-colored”.
Here is the link to try the new functionality: https://github.com/stefanutti/maps-coloring-java/releases/download/4ct/ct-ui-swixml-2.3-jar-with-dependencies.jar
Four videos for the four color theorem.
| music | coloring algorithm |
| slow motion maps | java application features |
Four Color Theorem 