Tag Archives: Alfred Bray Kempe

3-regular planar graph decomposition in cycles and 4CT

Posted on by
Reply

If you can prove that it is possible to decompose a 3-regular graph into cycles, all with even length, you have also proved the four color theorem.

I think this fact is already known, but I never paid too much attention to it before.

Naturally, also the opposite is true: since the 4CT is true, it means that it is possible to color it, and also get the Tait coloring. And for any two colors you choose (for example Red and Green), the related Kempe cycles form a partition of the graph and each cycle has an even number of edges.

Once the decomposition is found, since the cycles have an even number of edges, it is possible to color the edges of a cycle with two alternate colors (for example Red and Green), forming this way Kempe cycles. When all cycles are colored (with R and G), it is possible to use a third color (for example Blue) to color the remaining edges.

The resulting graph will have a Tait coloring for all edges, which is equivalent to coloring all faces with four different colors.

But, how difficult is it to find all cycles?

This one has 6 Red-Green cycles (all of even length), that form a division on the 3-regular planar graph into cycles.

Zoom on a planar graph, 10000 nodes, three-edge Tait colored

Posted on by
Reply

I generated a planar map of 10000 nodes and then colored using the 4ct python coloring program.

It did use Tait coloring (3-edge-coloring) which is equivalent to the four face coloring of the four color theorem.

It works pretty fast using:

  • graph reduction removing edges from F2, F3, F4, F5
  • graph rebuilding using Kempe chain color switching techniques

Four color theorem: about edges selection

Posted on by
Reply

For the decomposition of a graph representing a map, I’m trying to use different algorithms to select the edge to remove.

The question is:

  • When you have multiple valid choices, which is the best edge to select … if any?

Some basic rules are:

  • Avoid new F5 to be created
  • Get rid of F5 whenever is possible, selecting the edge of a face with 2, 3 or 4 edges
  • Consider to remove an edge from an F5 face only if no faces with 2, 3, 4 edges exist

Here are all possibilities. Last 2 groups (removing edges from F5 and F6) don’t have to be taken into account. I just wanted to see how it continued after the cases with faces made of 2, 3, 4 and 5 edges:

edges-selection-possibilities

Four color theorem: almost there?

Posted on by
1

Here there are some results that came out from the study of Kempe chains/cycles (of edges) in Tait coloring of a 3-regular planar graph.

Next is shown an image with a summary of the ideas behind this approach. I didn’t have the time to re-create this into computerized images. I will do it later. Soon will follow the F5 case for the part I’ve been experimenting with success (sub-condition where the two edges lies on two different Kempe-cycle – see below).

kempe-half-cycle-swapping-method

Here is the F4 case shown a little better:

kempe-half-cycle-swapping-method-F4

And here some deeper details of these ideas.

Theorem: In a well edge-colored (Tait coloring) 3-regular planar graph all Kempe chains are cycles

  • This can be easily proved showing that, once colored, the edges of any vertex use all the three colors (for example R, G, B), so if you are following the path of a Kempe chain, as for example an (G, B)-Kempe chain, the chain itself cannot end to a vertex, because one of the other two edges continues the kempe chain, unless that edge was exactly the first edge you started following the path of the chain … making it a Kempe cycle, as for example the (G, B)-Kempe cycle of this picture
  • Note: This theorem, in this form, is valid if the graph is already well colored (three colors). Consider that to say that the edges of a graph can be well colored (using three colors) is as difficult to prove as the four color theorem for the faces of a map. Never the less this result can be used to search a short proof of the four color theorem, even if it depends on the long proof ;-). Or (better) this result can be used without this dipendency on the long version, immerged in the reduction method when restoring the edges one at a time. As long as you solve the N+1 case (restore of F2, F3, F4, F5), starting from the map with only two faces (the island and the ocean surrounding it) the theorem is true

kempe-cycle

Picture-01: All Kempe-chains are Kempe-cycles

Steps and results toward a short proof of the 4ct:

  • Simplify the map removing one edge from one of the faces with 2, 3, 4 or 5 edges. Repeat this procedure until the map will have just one country left. This simplification procedure can be always done because the set { F2, F3, F4, F5 } represents an unavoidable set, so every 3-regular planar graphs has to have at least one face of the type included in the set
    • The procedure, for a simple map, is shown in the previous post: here
    • The idea is similar to the “patching” method used by Kempe, in which a “patch” with the same shape but a bit larger of a face (F2, F3, F4 or F5), was put over the face to shrink it down to a point. You can read the original paper here: On the Geographical Problem of the Four Colours
  • In reverse order, restore the edges that were removed, one at a time. Each time an edge is restore, we can face one of these conditions:
    • the edge restores an F2 – Note: particular and trivial case (see next point)
    • the edge restores an F3 – Note: trivial case
    • the edge restores an F4 – Note: Easy to handle
    • the edge restores an F5
  • F2 as a trivial case
    • When the restored edge reestablish an F2 face, it means the vertices of the resored edge, touch a single edge and so you have a spare color to use to solve this case (HAPPY END)
  • For all previous conditions (F2 can be seen as a particular case) there are two main possibile sub-conditions
    • CONDITION-1: The two edges touched by the restored edge are on a common Kempe cycle
      • If the two edges belong to a Kempe-cycle, the solution is easy. Apply a Kempe-chain color swapping to half (one of the two parts of the cycle being “cut” by the restored edge) of the cycle to solve this case (HAPPY END)
      • Consider that in case of the restored face is an F3, this is always the case, since the two edges touch each other. So also F3 can be regarded as a particular case
    • CONDITION-2: The two edges touched by the restored edge are NOT on a common Kempe cycle, but on distinct cycles … of course with no common edges
      • TBF: This is easy to handle for F4 and of course for F2 and F3 that are particular cases. For the F5 case I’m trying to prove that all cases can be reconducted to CONDITION-1

If this Example-02 the restored edge (in black) reestablish an F5 face. Both the edges (Green = on the left, Red = on the right) do non lie on the same (G-R)-cycle (CONDITION-2). Similar examples can be created when the two touched edges have the same color. In that case you can consider two different Kempe-chain ((R-x)-chain if the edges are colored Red) or you can easily reconduct that case to the one with different colors

kempe-cycle-F5-both-edges-not-on-cycles

Example-02: Example of restoring an F5

Now the diffucult part of the proof about the F5 case where the two edges do not lie on the same Kempe-cycle.

How can I reconduct a CONDITION-2 (edges NON on the same Kempe-cycle) to a CONDITION-1 (edges on the same Kempe-cycle)?

Four color theorem: back to the basics

Posted on by
1

Finally I bought two books about the four color theorem: “Four Colors Suffice: How the Map Problem Was Solved” by Robin Wilson e Ian Stewart; and the “The Four-Color Theorem: History, Topological Foundations, and Idea of Proof” by Rudolf Fritsch and Gerda Fritsch.

I am currently reading the first one, and I want to revisit the fundamentals by using the method Kempe employed when he believed he had solved the problem.

With these differences: I will approach it removing one edge at a time from F2, F3, F4, or F5 faces (unavoidable set) to reduce the map to two faces (including the ocean). Afterward, I will restore the edges in reverse order, consistently working with 3-regular planar graphs. Instead of applying Kempe’s chain color switching solely to the faces, I will consider Tait coloring of the edges and apply Kempe’s chain color switching to the edges.

Follow the arrow to visualize the steps:

kempe-reduction-and-kempe's-chain-v3.png

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.

Counting maps

Posted on by
Reply

I’ve posted this question on mathoverflow.

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

  • 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_3=7}^{s_4} \sum _{s_2=5}^{s_3} \sum _{s_1=3}^{s_2} s_1\left(s_1-1\right)\left(s_2-3\right)\left(s_3-5\right)\text{...}\left(s_{(f-3)}-((2f-5)-2)\right)

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 simmetrical maps):

  • 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 = 16 possible regular maps (with homeomorphics eliminated)
  • …

These are all maps up to 5 faces:

Are these different colorings?

Posted on by
Reply

UPDATE (18/Apr/2011)

The nunber of proper colorings (not considering permutations of colors) can be count using the “Chromatic polynomial” and dividing the result by 4! (factorial that counts the permutations). But, the chromatic polynomial is only known for few types of graphs (Triangle K3, Complete graph Kn, Petersen graph, …). I haven’t found papers on this problem. Highly propably, since the difficulty to find the Chromatic polynomial of complex graphs, there cannot be a direct formula to calculate how many different colorings exist.

I’ve posted this question here on mathoverflow.

END UPDATE

Take a look at these three graphs:

Are these really different colorings?

Before to dismiss this, do the following on the first graph:

  • Change Blue to Yellow (Blue was just an arbitrary color among infinite others)
  • Change Green to Blue
  • Change Yellow to Green

Now you have the second graph. Continue with this:

  • Change Green to Yellow
  • Change Red to Green
  • Change Yellow to Red

Now you have the third graph. Since the arbitrary nature of the choice of colors, the first graph could have been colored as the third one since the beginning.

The same result, can be obtained by changing all three colors of the first graph to three other colors. If applying the same method to the third graph, you can get the same configuration for the two graphs, it means that they can be considered, for some areas of investigation, as the same configuration.

There are more complex cases in which swapping colors won’t help to get from one coloring to the other.

In the following picture taken from http://en.wikipedia.org/wiki/Graph_coloring, the graphs named (A) and (B) are the only ones that cannot be converted into one another by swapping colors.

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

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?