## Four color theorem: 3-edge coloring, impasse and Kempe chain color swapping

It is known that for regular maps, “3-edge coloring” is equivalent to finding a proper “four coloring” of the faces of a map.

This post is about coloring impasses, fallacious Kempe chain color swapping (not solving the impasse) and an hypothesis I’d like to verify.

FIRST: What is an impasse

Lets say you are coloring (Red, Green, Blue) the edges of a map and have properly colored a portion of it, as in the example. At a certain point you get to a vertex that has two edges already colored, for example with Red and Green (e1, e2). In this case you’d be forced to select the color Blue for the uncolored edge (ex). But it is possible that the color Blue is already used by one of the other two edges starting from vy (e3). This situation is called impasse. In the example e4 may be already colored or not, the impasse remains.

SECOND: Apply Kempe chain color swapping and problems using it

One technique that can be used to solve an impasse is to apply a Kempe chain color swapping. But the problem is that this Kempe swap does not always work. This happens when the Kempe swap does not only change the color of the edge that caused the impasse (e4), but also the color of one of the other three edges involved in the impasse (e1, e2, e5 in the example).

To better understand Kempe chain color swapping, lets analyze, step by step, the labeled part the graph showed above:

• Impasse: Since e1 and e2 are colored Green and Blue, e3 should be colored Red. But this color can’t be used because Red is already used by e4
• To solve this impasse you can try to apply a Kempe chain coloring swapping
• The possibilities are: (R-G)-chain and (R-B)-chain that change the color of e4
• (R-G)-chain, involving e4 and e5 would not work, because R would end up in e5, not changing the situation … even if the continuation of the chain arrives to the vertex a
• (R-B)-chain has a better chance to work, because would set e4 with color B, sometimes solving the impasse. I said sometimes because this is true only if the (R-B)-chain does not arrive to vertex b, swapping also the color of e2, in which case would simply mirror the problem between the vertices c and d

THIRD: Hypothesis to solve the second impasse when Kempe swap fails

Using the Java application I wrote a started experimenting Kempe chain color swapping and I found many situation where the swapping would not solve the impasse, but I also found a method, which of corse needs to be proved, to solve the second impasse when Kempe chain color swapping fails (fallacious Kempe chain color swapping). If true (consider that what is written in this blog are just personal notes about an attempt) this would prove the four color theorem a very short and elegant way.

<insert video>

Hypothesis:

The hypothesis I’d like to verify is that from maps in which F2, F3, F4 faces have been previously removed (which is safe for the proof of the theorem), the fallacious Kempe chain can always be “broken” (or in different words: its path changed) along the way (using another Kempe chain coloring swap) to avoid the second impasse. After this “cut”, the original swap can be performed to solve the original impasse.

I tried this method on many maps with and without F2, F3, F4 faces, and so far it seems to work … always.

Here is an example:

In this example:

• There is an impasse between Vx and Vy. On Vx color Green could be used for the edge connecting Vx and Vy but Green is already used by e4
• (G-R)-chain (…-e4-e3-…) swap does not work because, e4 and e3 will simply swap colors and Vy will still have a Green color starting from it
• (G-B)-chain (e4-e5-…) swap does not work because the chain ends up to e1 (to the vertex Vx) and the impasse will remain
• The hypotesis, that works for this example and all examples I found (maps without F2, F3, F4), is that che (G-B)-chain can be “broken” using a color swapping of the (B-R)-chain at (…-e5-e6-…), and after this swap you can apply the original (G-B)-chain color swap, that will solve the impasse. By contrary I found many example for maps containg F2, F3, F4 in which this hypotesis is not true

To be finished:

• Insert example of maps containing F2, F3 or F4 where the second Kempe chain swap does not solve the impasse
• Insert other examples of impasses with maps without F2, F3, F4
• Insert video examples of impasses with maps without F2, F3, F4, that can be solved by “cutting” the fallacious chain

## Four color theorem: Tait edge coloring and Kempe switch

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).

## 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.

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

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

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