Four color theorem: Tait edge coloring


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://sourceforge.net/projects/maps-coloring/

Advertisements
This entry was posted in math and tagged , , , , , , , , , . Bookmark the permalink.

11 Responses to Four color theorem: Tait edge coloring

  1. See below-left figure for the illustration edge 3-coloring of a bridgeless cubic planar graph directly by using spiral chain. http://www.flickr.com/photos/49058045@N00/6548801051/in/photostream

    Link to the paper: http://arxiv.org/abs/math/0507127
    Spiral Chains: The Proofs of Tait’s and Tutte’s Three-Edge-Coloring Conjectures

    Like

    • stefanutti says:

      I would really like to study the method you have found to color maps. As far as I know, it is the only teoretical and practical method, other than brute force, that I found on internet to color maps. I’d like to (if I find a little time) implement the algorithm on the Java application I’am building.

      Like

  2. From four coloring to edge 3-coloring see (http://www.mathpuzzle.com/4Dec2001.htm)

    Like

  3. stefanutti says:

    What I would like to do is to take an uncolored map (rectangular or circular), find the spiral chain and than color the map, both (spiral chain and coloring) using your method. Do you think is it possible to program the algoritm?

    Like

    • Cahit says:

      Step 1. (Spiral Chains) Uncolored map is a cubic map M (bridgeless cubic planar graph G_m). Hence, G can be drawn as a cubic plane graph G_m. Select an arbitrary outer-boundary vertex as a starting vertex of the spiral chain S_1. The set S of spiral chains S_1, S_2, …, S_k can be found in a similar way to the vertex coloring of the maximal planar graph, but this time for the bridgeless cubic graph G_m.

      Step 2. (Spiral Chain Edge-coloring). Let C={Green, Yellow, Blue}. While coloring an edge e of G_m, the color green G has priority over the colors yellow Y and blue B. And color yellow Y has priority over blue B. Then, color the edges of S_1, S_2, …, S_k starting from the first edge of S_1. Note that we color a backbone edge (spiral chain edge) first and then the hair (non-spiral chain edge). If a color conflict arises at some vertex use appropriate backward Kempe-chain color switching in order to resolve the conflict. When all edges of S are colored we have an edge 3-coloring of G_m.

      See: “On the_Algorithmic Proofs of the Four Color Theorem, Section 3”

      http://neu-tr.academia.edu/IbrahimCahit/Papers/539878/On_the_Algorithmic_Proofs_of_the_Four_Color_Theorem

      Like

  4. Finding a set of disjoint spiral chains that covers all vertices in an uncolored map (rectangular or circular) can be easier than any plane embedding of the same graph since rectangular and circular graph is more structured.

    Like

    • stefanutti says:

      Some notes about what I’m doing:

      http://maps-coloring.git.sourceforge.net/git/gitweb.cgi?p=maps-coloring/maps-coloring;a=tree;f=ct/ct-docs/cahit-spiral-chains

      So far I’m still stuck trying to understand how to apply spiral chains to bridgeless cubic graphs instead of maximal planar graphs. Do I have to triangularizate the cubic graph first?

      I new version of the java application is available with these new features: save and restore maps (metadata), force coloring of faces to find different colorings of the same map, faster coloring, …

      http://sourceforge.net/projects/maps-coloring

      Like

      • Illustration of spiral chain edge three coloring on the Grinberg-graph:

        Edge three coloring of the Grinberg graph

        Here is a short explanation of the edge-three coloring of the Grinberg graph (3-colored graph (2005) of my new year card (see my December 27, 2011 post above)) by using spiral chain. First we choose any veartex of the outer face as a start vertex for the spiral chain as well as edge coloring. Note that the graph is plane embedding (no edges cross) of a bridgeless cubic planar graph. In the figure START and END vertex for the spiral chain have shown by an star in dark-blue. Furthermore spiral chain is constructed in clock-wise direction. Since here we have only one spiral chain that is also hamiltonian path (shown in the figure by directed edges).

        Now spiral chain edge coloring start from the edge incident at the START vertex and the set of three colors is {Green, Orange, Red}. Whenever we have a not yet colored edge along the spiral chain we try it color with Green if it is not possible with Orange and if it is not possible with Red and if it is not possible (that is in case of “color conflict” or needing the fourth color for a proper coloring) we use appropriate backward Kempe-switching for color pairs (Red, Orange) and (Orange, Green)). In the Grinberg graph these backward Kempe-swithing have been used three times and shown with dotted-edges of three sub-paths. They are K_3(Red, Orange), K_2(Red, Orange) and K_1(Orange, Green).

        Edge three coloring of the Grinberg graph

        From the mail:

  5. Thanks Mario for adding the part from my mail to the above post. The bottom line is
    “Four proofs of the four color theorem by using spiral chains”

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s