Tag Archives: 4ct

Optimizing Graph Coloring with Reinforcement Learning

Posted on by
Reply

This is what I will be working for a while. Restart is difficult, but necessary.

Why use Reinforcement Learning for Graph coloring?

In my Python application, that works on 3-regular planar graph, deciding which is the order of the edges to remove can be non-trivial. A naive approach randomly picks edges from F2 faces, F3, F4 or F5. This is the approach I used :-(. It leads to impasses when rebuilding the map. See https://4coloring.wordpress.com/2014/08/27/four-color-theorem-experimenting-impasses-as-in-life/

But a reinforcement learning agent can learn to make better selections over time to reduce color conflicts, I hope :-), and shed light on some properties of the graph that can be used in the proof.

The code will be here: https://github.com/stefanutti/maps-coloring-python

Remove one edge at a time from F2, F3, F4, or F5 faces. These faces represent the basic unavoidable set. This process will reduce the map to three faces, including the ocean as the external area. Afterward, I will restore the edges in reverse order, consistently working with 3-regular planar graphs. I will consider Tait coloring of the edges and apply, when necessary, Kempe’s chain color switching to the edges.

Remove edges a then restore them

For the Agent:

  • Environment initialization = The starting uncolored 3-regular planar graphs
  • Action = Select the edge to remove from the 3-regular planar graphs
  • State = The updated 3-regular planar graphs
  • Reward = +1 if Random Kempe’s chain color switching was not necessary, -1 otherwise

4CT and loops, cycles, circuits, chains, paths

Posted on by
Reply

I realized that for some posts I may have used “Kempe loops” and “Kempe cycles” to describe closed “Kempe chains”, that in other words form closed paths (cycles). I think it would have been better always to use “Kempe cycles”.

https://en.wikipedia.org/wiki/Loop_(graph_theory)

https://en.wikipedia.org/wiki/Path_(graph_theory)

https://en.wikipedia.org/wiki/Hamiltonian_path

Non-Hamiltonian 3-regular planar graphs, Tait coloring and Kempe cycles … what else ;-)

Posted on by
Reply

Considering the smallest known non-Hamiltonian 3-regular planar graphs, discovered by Barnette-Bosák-Lederberg, I computed the Tait coloring and then deformed it to put in evidence the R-G cycles that in this case are four.

Links to the historical importance of this graph:

https://mathworld.wolfram.com/Barnette-Bosak-LederbergGraph.html

https://en.wikipedia.org/wiki/Barnette–Bosák–Lederberg graph

And here is the Tait coloring of this graph:

Deformed here to better show the R-G cycles:

Tait coloring and the four color theorem: personal Q&A

Posted on by
Reply

Some questions about the previous post:

Q1) Can cycles be concentric?

Yes, see this example.

Q2) Verify if at least one of the cycles (R-G, R-B, or G-B) form an Hamiltonian circuit

False.

From the Tait’s conjecture we now know (now = 1946 by William Thomas Tutte) that 3-regular graphs exist also without an Hamiltonian circuit. It means that, no matter what, it is not possible to find a cycle that touches all vertices, and therefore no single Kempe cycles of any two color selection, can exist.

From Wikipedia, the free encyclopedia

This article is about graph theory. For the conjectures in knot theory, see Tait conjectures.

In mathematics, Tait’s conjecture states that “Every 3-connected planar cubic graph has a Hamiltonian cycle (along the edges) through all its vertices“. It was proposed by P. G. Tait (1884) and disproved by W. T. Tutte (1946), who constructed a counterexample with 25 faces, 69 edges and 46 vertices. Several smaller counterexamples, with 21 faces, 57 edges and 38 vertices, were later proved minimal by Holton & McKay (1988). The condition that the graph be 3-regular is necessary due to polyhedra such as the rhombic dodecahedron, which forms a bipartite graph with six degree-four vertices on one side and eight degree-three vertices on the other side; because any Hamiltonian cycle would have to alternate between the two sides of the bipartition, but they have unequal numbers of vertices, the rhombic dodecahedron is not Hamiltonian. The conjecture was significant, because if true, it would have implied the four color theorem: as Tait described, the four-color problem is equivalent to the problem of finding 3-edge-colorings of bridgeless cubic planar graphs. In a Hamiltonian cubic planar graph, such an edge coloring is easy to find: use two colors alternately on the cycle, and a third color for all remaining edges. Alternatively, a 4-coloring of the faces of a Hamiltonian cubic planar graph may be constructed directly, using two colors for the faces inside the cycle and two more colors for the faces outside.

Smallest known non-Hamiltonian 3-regular planar graph: https://mathworld.wolfram.com/Barnette-Bosak-LederbergGraph.html.

Next post will be on the four coloring of the barnette-bosák-lederberg graph, which is the smallest known non-Hamiltonian graph, and the analysis of its Kempe cycles.

Q3) What about if I start with finding cycles, of even length (# of edges), that cross all vertices?

Some initial considerations: If cycles have to fit with Kempe cycles (closed paths of two alternating colors), they have to be of even length, and that would also mean that the total number of vertices crossed by all the cycles of the same two colors should be even too. Is it like this, or am I missing something? What about graphs with an odd number of vertices? Am I missing something?

Answer to the initial consideration: https://math.stackexchange.com/questions/181833/proving-that-the-number-of-vertices-of-odd-degree-in-any-graph-g-is-even + https://math.stackexchange.com/questions/181833/proving-that-the-number-of-vertices-of-odd-degree-in-any-graph-g-is-even

Finding cycles seems to be as difficult as finding a solution for of 4 coloring problem 😦

Generate planar graphs

Posted on by
Reply

There are some methods around to create planar graphs. One of these is based on the Delaunay triangulation algorithm from which you can derive its dual, a 3 regular planar graph. Tools and libraries that I found around (sage, networkx and others), permits you to save the graph using one of common format to represent the graph itself, specifically: .dot, .graphml, .GEXF, .gpickle and others). One problem that I found is that if I save the graph I loose the planar representation of it.

Since for what I am trying to do, namely demonstrate with pencil and paper that the four color theorem has a simpler demonstration, I need to work directly with the planar representation of the graph.

I decided to implement my own method (based on edge addition to planar graphs. See “John M. Boyer and Wendy J. Myrvold, On the Cutting Edge: Simplified O(n) Planarity by Edge Addition. Journal of Graph Algorithms and Applications, Vol. 8, No. 3, pp. 241-273, 2004.”) to generate an save the graph directly using its planar representation. Get the code here at: https://github.com/stefanutti/maps-coloring-python. The program generates random planar graphs without using graphs library and most importantly without using complex algorithms, as planar embedding or planarity testing.

Planar embedding: “A combinatorial embedding of a graph is a clockwise ordering of the neighbors of each vertex. From this information one can define the faces of the embedding”.

sage: T = graphs.TetrahedralGraph()
sage: T.faces({0: [1, 3, 2], 1: [0, 2, 3], 2: [0, 3, 1], 3: [0, 1, 2]})
[[(0, 1), (1, 2), (2, 0)],
[(3, 2), (2, 1), (1, 3)],
[(3, 0), (0, 2), (2, 3)],
[(3, 1), (1, 0), (0, 3)]]

Edge addition can start from a basic graph of four faces (bottom right). In the third last line of this picture I added edges from a graph with 3 faces and 2 vertices (considering the ocean). But as you can deduct from the other pictures I can safely start from a graph with 4 faces and 4 vertices (bottom right).

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