Tag Archives: 4ct

Four color theorem: experimenting impasses (as in life)

Posted on by
1

I still think a solution may be found in Kempe chain color swapping … for maps without F2, F3 and F4 faces (or even without this restriction).

Or at least I want to try.

kempe-chain-impasse-v2

How you can solve the impasses (To be finished):

To explain the possible cases, without lack of generality, I can assume to start with these colors: e1=red, e2=green, e3=blue, e4=red. e4 may also be colored in green, the reasoning will not change much.

  1. If e3 and e4 are not colored … there is no impasse → OK
  2. If e3 is the same color ex should be (blu in the example) and e4 is non colored
    1. If one of the two possible chains starting from e3: (b, r)-chain or (b, g)-chain does not end at e1 or e2
      1. Use it to swap the color of e3 and solve the impasse → OK
    2. If both end at e1 or e2
      1. Try to deroute one of the two chains, using another kempe chain color swapping along the way, to fall into one the the solvable cases (2.A)
        1. If the derouted original chain does not longer end at e1 or e2, then apply the original kempe chain color swapping and solve the impasse → OK
        2. If deroute does not work
          1. … TBV: It seems that swapping colors around solve all type of impasses
  3. If e3 is the same color ex should be, and e4 is also colored
    1. In this case the chain (…-e3–e4-…) = (b, r)-chain would simply swap the colors of e3 and e4 and therefore will not solve the impasse. It is better to use the other (b, g)-chain, starting from e3
      1. If this chain does not end at e2 (e1 is not a possible end because the chain is blue and green), use it to swap the color of e3 and solve the impasse → OK
      2. If it ends at e2
        1. Try to deroute the chain, using another kempe chain color swapping along the way, to fall into one the the solvable cases
        2. If deroute does not work
          1. … TBV: It seems that swapping colors around solve all type of impasses

A deroute of a chain appears as in the next picture. Consider that deroutes may not work because Chain-B color swapping may change one or more of the three edges e1, e2, e4, and after appying the Chain-B swap, the chain starting with a3, may still end to one to e1, e2, e4. See this post for a real example: here.

kempe-chain-deroute-v2

About swaps of a partially colored map, I’ve asked a question on mathoverflow … here.

Maybe I was wrong when, in the motivation of the question (mathoverflow), I said that “I found many examples in which Kempe chain color swapping does not work for maps with faces of type F2, F3, F4, but I did not find an example of maps with only F5 or higher“. It seems to be possible also for maps with F2, F3, F4.

I’ll continue to search for counterexample but, for what I’ve seen so far (I tryed about 50 maps) it has been always possible to solve impasses, only proceeding by swapping colors.

This is one of the map that I thought to be a counterexample, but it is not. Its signature is:

  • 1b+, 9b+, 9e+, 3b+, 5b+, 7b+, 12b+, 10b-, 11b-, 5e-, 7e-, 4b-, 3e-, 2b-, 10e-, 4e-, 6b-, 11e-, 12e+, 8b+, 8e+, 6e+, 2e+, 1e+

impasse-in-map-not-simplified

Something else to check:

  • Since once completely colored, all chains are actually loops, when it comes to the last two impasses, if you solve one impasse also the other one gets solved!

Four color theorem: counterexample to the hypothesis I was verifying :-(

Posted on by
2

Bad news … to me!

This example it is a counterexample to the hypothesis I was trying to verify!

Map signature: 1b+, 4b+, 6b+, 15b+, 7b-, 14b-, 8b-, 12b-, 13b-, 11b-, 9b-, 8e-, 7e-, 5b-, 6e-, 9e-, 10b-, 5e-, 4e-, 3b-, 10e-, 11e-, 12e-, 3e-, 2b-, 13e-, 14e-, 15e+, 2e+, 1e+

😦

For this example, no Kempe color switching exists along the main chain (b-r) = (1-2-3-4-5-6-7-8) that “divert” it, to make it end at a different vertex than vx. All other chains (*-g) along the main chain (b-r) involve vx or vy.

hypothesis-counterexample-v2

Four color theorem: simplified maps and fullerenes (answer)

Posted on by
Reply

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

Posted on by
1

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 (github):

  • 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

Posted on by
Reply

😦

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)

Posted on by
Reply

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 github site.

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

Four color theorem: Cahit spiral chains

Posted on by
Reply

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 (changing the starting point)
  • 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 <– DONE

Here is the video on youtube:

Four color theorem: other representations of maps

Posted on by
Reply

Here are some new representation of graphs:

Thanks to:

Four color theorem: representations of maps

Posted on by
5

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

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)
  • …

New representations (answers from mathoverflow):

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

See next post for other representations.