User mario stefanutti - MathOverflow

Question about 3-regular graphs with a restriction (also fullerene and four color theorem)

2013-01-29T00:01:54Z

(Crossposted from math.stackexchange.)

Studying all 3-regular graphs that have only faces with 5 edges or more (simplified), I empirically found (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 being created, 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?

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)
- he 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: ???

ADD (28/Jan/2013):

Images of these graphs are here: http://4coloring.wordpress.com/2013/01/26/four-color-theorem-simplified-maps-and-fullerenes/

How many "different" colorings (excluding exchanges) exist for a given map (graph)?

2011-04-10T17:07:22Z

In particular I'm interested in regular maps, excluding all maps that can be colored with 2 or 3 colors. For what I need to analyze, maps have to be regarded as differently colored, if the same coloring cannot be obtained by subsequent exchanges of colors. In other words, for example, once a map has been properly colored, I don't want to count all other configurations that derive from subsequent exchanges of colors. Since the arbitrary nature of choosing colors, these derived configurations are equivalent (for what I'm analyzine) to the first one, since they could have been obtained just choosing different colors in the first place. Instead, there are colorings that differ in such a way that exchanging colors won't help to transform one configuration into the other. In the following picture the graphs named (A) and (B) are the only ones that cannot be converted into one another by swapping colors.

http://4coloring.files.wordpress.com/2011/04/3-colored-in-12-different-ways.png

My question is: how many "different" colorings (in the meaning I explained) exist for a given map? I've only found an article on http://en.wikipedia.org/wiki/Graph_coloring that count all possible colorings including swaps. Is there a paper that can help me on this?

I already posted it to "math stackexchange" but, so far, I haven't received the answer I was looking for.

Representations of regular maps (four color theorem)

2011-05-03T23:20:50Z

For the scope of the four color problem and without lack of generality, maps can be represented in different ways. This is generally done to have a different perspective on the problem.

For example, the graph-theoretic representation of maps has become so common and important that generally the four color problem is stated and analyzed directly in terms of graph theory: http://en.wikipedia.org/wiki/Four_color_theorem.

I am trying to collect other representations that may in some way help to get a different point of view on the problem. If you know one of these representations that is not listed and wish to share, report it here. If you also have a web reference that explains or shows the representation, it would be great.

The representations have to be general and applicable to all maps with the simplification that only regular maps (no exclaves or enclaves, 3 edges meeting at each vertex, etc.) can be considered.

These are some classic representations:

Natural: As a 3-regular planar graph (boundaries = edges)
Canonical: As the dual graph of the "natural" representation (region = vertex, neighbors = edges)
As a straight line drawing graph (Fáry's theorem)
As a graph with vertices arranged on a grid
As a rectilinear cartogram
As circle packing

Plus, I found these:

As a circular map
As a rectangular map
As clefs (derived from rectangular maps)
As pipes map (derived from the clefs representation)
...

Here is an example of some of these representations for the original map shown:

And here are other representations after the comments received:

UPDATE: 19/May/2011 - Added other representations of graphs

Is there a formula to count how many different topological regular maps can be created with n faces (on a sphere)?

2011-04-19T19:58:06Z

Notes:

For "regular" I intend maps in which the boundaries form a 3-regular planar graph
For "different" I intend maps that cannot be topologically transformed one into another (faces have to be considered unnamed)

I've been looking for a formula, but it is too difficult for me. Maybe it has a simple solution but I don't see it.

This was my best guess, but I already know that it is not correct because full of symmetries, as it can be verified manually.

General formula:

$2\sum_{s_{(f-3)}=2f-5}^{2f-5+2} \text{...}\sum_{s_2=5}^{s_3} \sum_{s_1=3}^{s_2} s_1\left(s_1-1\right)\left(s_2-3\right)\text{...}\left(s_{(f-3)}-(2f-5-2)\right) $

Examples:

4 faces = $2\sum_{s_1=3}^5 s_1\left(s_1-1\right) $
5 faces = $2\sum_{s_2=5}^7 \sum_{s_1=3}^{s_2} s_1\left(s_1-1\right)\left(s_2-3\right) $

Here are the first results that can be found manually (excluding symmetries):

2 faces = 0 possible regular map (an island and the ocean) (not to be counted, because not regular)
3 faces = 1 possible regular map (an island with two regions and the ocean) (two islands and the ocean wouldn't be regular)
4 faces = 3 possible regular maps (can be verified adding a face from the previous map)
5 faces = ~~20 possible regular maps~~ (ERROR: There were duplicates)
6 faces = ~~329 possible regular maps~~ (ERROR: There were duplicates)
...

These are all maps up to 5 faces (ERROR: contains duplicates):

Image for the comment on "triangulations of the sphere"

And without duplicates:

MODIFIED: 20/Apr/2011 - Removed "3-connected" from the question. See comment below.

MODIFIED: 21/Apr/2011 - Added a picture with all regular maps up to 5 faces

MODIFIED: 21/Apr/2011 - Added a picture for the comment on "triangulations of the sphere" and multiple edges, related to the dual graph of the original 3-regular planar graph

MODIFIED: 27/Apr/2011 - Manually computed number of different maps of 6 faces = 329, added numerical IDs to the maps

MODIFIED: 29/Apr/2011 - The manual computation of the number of regular maps contains some duplicated (Homeomorphic pairs)

MODIFIED: 29/Apr/2011 - Just to leave things a little more clean (I removed the duplicates ... I hope)

Comment by Mario Stefanutti

2013-02-08T22:20:17Z

Thanks again. Plantri is really a great program and it is so fast. Where my program takes 1 minute to elaborate all graphs of 15 faces, Plantri is istantaneous.

Comment by Mario Stefanutti

2013-01-29T09:58:14Z

Thanks. So fast! I'm going to try this program right away.

Comment by Mario Stefanutti

2011-06-28T14:48:58Z

Hi, how did you make these computations? I was planning to implement this feature into the program I'm building, but I'm having trouble to eliminate maps that "seems" different but that are actually the same map (Homeomorphic maps). See this other post: mathoverflow.net/questions/62328/…

Comment by Mario Stefanutti

2011-05-06T17:17:38Z

I really like this one based on the circle packing theorem, thanks!

Comment by Mario Stefanutti

2011-05-04T10:34:47Z

Hi Paul, I remember a comment made about this question by Noah Snyder. mathoverflow.net/questions/19240/…. "As far as I know there isn't anyone who is holed up in their attic thinking about only the 4-color theorem, instead there's a lot of people who every time they find a new tool think: hrm, I wonder if this tool would work on the 4-color theorem?" For example check the current reserch of Robin Thomas (people.math.gatech.edu/~thomas)

Comment by Mario Stefanutti

2011-04-27T18:04:55Z

I think I located one of the pair you were talking about: 1.1.8 and 1.3.4. You are right, these are the same map! I have to review the manual computation of the count of different maps. I still would like to find a formula to count different maps, avoiding to manually calculate them ... also because this is error prone! Thanks!

Comment by Mario Stefanutti

2011-04-27T17:40:51Z

Hi jc, I added some numerical IDs to the maps. I wasn't able to pinpoint the pairs you were talking about. Can you specify them using the IDs? I just want to be sure we talk about the same pairs of maps.

Comment by Mario Stefanutti

2011-04-27T14:18:16Z

Actually it matches this one: oeis.org/A163138 (0 does not have to be considered because the map in that case is not regular). But I think 4 terms are just too few and it may be just a coincidence.

Comment by Mario Stefanutti

2011-04-21T16:50:24Z

Two things I am thinking. I have to analyze them better, but for sure you can help me before I'll find the answer myself. The first thing is that maps are usually represented using the graphs without considering multiple edges, which is good for coloring but I am not sure abount counting. For example, considering multiple edges the dual graph wouldn't have triangular faces. The second thing is about reversibility: do all triangulations have duals 3-regular planar graphs? ![maps and triangulations](4coloring.files.wordpress.com/2011/04/…)

Comment by Mario Stefanutti

2011-04-21T07:16:14Z

I made a correction to the question (as pointed out by jc). I was interested in "regular maps" without forcing 3-vertex-connectivity. Sorry for the mistake. The abstract of the paper reports: "In the paper, we enumerate three classes of cubic planar maps with no loops or multiple edges: 1-connected; 2-connected; 3-connected and triangle-free." The results I found manually give these results for 3, 4 and 5 faces: 1 maps, 3 maps, 20 maps.

Comment by Mario Stefanutti

2011-04-19T22:32:17Z

Yes, you are correct. My mistake. I want to consider only "regular maps" without forcing 3-vertex-connectivity. Only vertexes having 3 edges. For example in the next picture, starting from a map of four faces (3 + the ocean) and adding one face, I would like to count maps excluding those generated from symmetries. 4coloring.files.wordpress.com/2011/04/… I'll remove 3-connected from the question.

Comment by Mario Stefanutti

2011-04-12T15:07:24Z

Printed. I'm not that expert but I'll try to read it. Thanks!

Comment by Mario Stefanutti

2011-04-12T15:06:10Z

Thanks for the answer. I inserted a note to comment made by "Thierry Zell". It applies also to this comment. Thanks again.

Comment by Mario Stefanutti

2011-04-12T15:02:55Z

@all: Thanks for the info. Yes, it is the problem I'm facing. But to get the "number of colorings" the only method I found is to compute the chromatic polynomial, which is known only for few graphs and it is hard to find for more complex cases. Do you know of papers that directly approach the computation of the "number of colorings without exchanges of colors"? I've implemented a brute force algorithm to color a given map with four colors. I'll try to extend it to find all possible colorings manually ... excluding exchanges. youtube.com/user/mariostefanutti#p/u/2/…