Four color theorem: new video and new software

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 here: sourceforge.

Using it, I generated all simplified graphs, in graphml format, up to 18 faces:

• all-graphs-up-to-18.rar-rename-to-rar.doc

Here is the video on youtube:

Four color theorem: simplified maps and fullerenes (answer)

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:

• 3 on 16 faces (as you said)
• 4 on 17 faces
• 12 on 18 faces
• 23 on 19 faces
• 73 on 20 faces

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

Four color theorem: simplified maps and fullerenes

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 (), do not actually exist. Using a VF2 algorithm to filter out isomorphic maps, I also noticed that not so many graphs as I expected exist. 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 very long time (days of CPU time on a PC), is this sequence already known?

I did post this question on: math.stackexchange.com

• 12 faces: 1 (only 1 graph exists)
  • On 3 dimentional space (sphere) it is a dodecahedron
  • It is a fullerene: 20-fullerene Dodecahedral graph
• 13 faces: 0 (no simplified graphs exist with 13 faces)
  • The hypothetical (by Euler’s identity) map of 12 F5 and 1 F6 does not exist
• 14 faces: 1 (12 F5 + 2 F6)
  • The hypothetical (by Euler’s identity) map of 13 F5 and 1 F7 does not exist
  • It is a fullerene: GP (12,2) Generalized Petersen graph
• 15 faces: 1 (12 F5 + 3 F6)
  • The hypothetical (by Euler’s identity) map of 14 F5 and 1 F8 does not exist
  • It is a fullerene: 26-Fullerene
• 16 faces: 3 (Two graphs are 12 F5 + 4 F6. The other has 14 F5 + 2 F7)
  • The hypothetical (by Euler’s identity) map of 14 F5 and 2 F7 does exists
  • The other two are Fullerenes
• 17 faces: ???
• 18 faces: ???
• 19 faces: ???
• 20 faces: ???

Many fullerenes are here: 
http://hog.grinvin.org/Fullerenes
.

Last things implemented in the Java program (sourceforge):

• Save and restore all lists (maps and todoList) to disk
  • Done: 19/Gen/2013
• Verify the various filters when generating maps
  • Done: 19/Gen/2013
• Browse the todoList
  • Done: 20/Gen/2013

---

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

Four color theorem: work in progress

Too many more things to do and little time:

• Filter out duplicates. I finally found a java library to efficiently filter out all isomorphic graphs. It is a library part if the sspace project. Using it I will be able to test more complex simplified maps with lots of vertices … not risking to spend CPU time on duplicates
• Finish the implementation of the Cahit algorithm to color the edges of a bridgeless cubic planar graph. I still need to well understand why Kempe’s chain color switching works using Cahit spiral chain method … especially when there is more than one spiral chain
• Convert the swing application to javafx. This way I’ll be able to eliminate many third party dependencies: G, swixml, …
• …

Bye

Four color theorem: Cahit spiral chains (step two)

Now the application is able to find all spiral chains of a graph.

I still need to:

• Implement the Cahit coloring algorithm using the spiral chains
• Add some additional features to the Java application
  • Modify the settings to color the edges
  • Manual selection of the starting vertex
  • Manual coloring of the Edges
  • …

The application can be downloaded from the sourceforge site.

About the Cahit coloring algorithm there are some things that I need to undestrand before to implement the Java code.

Four color theorem: Cahit spiral chains

Hi,

I’ve found some time to implement the first version of Cahit Spiral Chains algorithm.

I still need to:

• Find all spiral chains of a given graph and not only one first one. I need to implement the concept of “nearest unused vertex to the last vertex of the last spiral chain”. This is needed to find the starting point of the next spiral chain
• Implement the Cahit coloring algorithm to find the Tait coloring of the given graph

Here is the video on youtube:

Four color theorem: deep analysis of a map

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

Here is the question on: math.stackexchange.com

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’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: mathoverflow.net

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:

!

What I know is that:

• Since the colors of three neighbors 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: