Tag Archives: Graph theory

Four color theorem: down to a single case!

Posted on by
Reply

This post follows directly the previous one. I’m down to a single case to prove (pag. 3).

kempe-half-cycle-swapping-method-F5-third-page-v2

I think I should move to Java coding, implementing the entire algorithm: map reduction (removing edges), color reduced map, restore of edges one at a time, adjust the coloring to the case to prove (e2 = red), apply Kc5 color switching, …, apply the half Kempe-cycle color switching.

Notes (pag. 1 and 2):

kempe-half-cycle-swapping-method-F5-first-page

Second page:

kempe-half-cycle-swapping-method-F5-second-page

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

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: Tait edge coloring

Posted on by
11

From Wikipedia: “The four color theorem, on vertex coloring of planar graphs, is equivalent to the statement that every bridgeless 3-regular planar graph is of class one (Tait 1880). This statement is now known to be true, due to the proof of the four color theorem by Appel & Haken (1976).”

Here is a simple implementation of this equivalence, that converts a map from “4-face-colored” to “3-edge-colored”.

Here is the link to try the new functionality: https://github.com/stefanutti/maps-coloring-java/releases/download/4ct/ct-ui-swixml-2.3-jar-with-dependencies.jar