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 (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

  • 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
About these ads
This entry was posted in math and tagged , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s