# maps with a large number of 4-colorings

I brought this up in January, but now know more and can be more precise.

I will have two questions.

1. How much of this is known?

2. If you don't know the answer to 1, then who does?

I invite all responses, but ask that you put a "reliability" measure on your answer. That will help immeasurably.

Now for the description of the above mentioned this.'

The maps considered are planar, connected, cubic and with common restrictions that are easier to state in terms of the dual map. The dual map (which will be a triangulation) is required to have no closed paths of lengths 1 or 2 and all closed paths of length 3 are required to be boundaries of triangles. Many will recognize this hypothesis from a theorem of Whitney.

4-colorings of the regions of a given map are considered the same if a permutation of the colors makes the colorings the same. If two colorings fail this test, then they are considered different even if an automorphism of the map makes the colorings the same.

In our class of maps, we consider maps of $n$ regions. We let $m_1(n)$ be the largest integer that is the number of 4-colorings of a single map. We let $m_2(n)$ be the second largest integer that is the number of 4-colorings of a single map. We continue to $m_3(n)$ and $m_4(n)$.

It is known that counting all colorings of all maps is computationally hard. (Reference found in another MO discussion and available on request.) Note that I am only asking about the maps with large counts.

Further discussion requires the Jacobsthal numbers (A001045 in the On-Line Encyclopedia of Integer Sequences). They satisfy $$J(0)=0,\ J(1) = 1, \ J(n+1) = J(n)+2J(n-1).$$ Compute a few values to learn much about them.

Our observations about the $m_i(n)$ show they are heavily dependent on the parity of $n$. We record conjectures' that use pairs $(e(n), \ o(n))$ where $e(n)$ gives the values for even $n$ and $o(n)$ gives the values for odd $n$.

The following seem to be true: $$m_1(n) = (J(n-3)+1, \ J(n-3)), \ \ \ n\ge 5,$$ $$m_2(n) = (m_1(n-1)+7, \ m_1(n-1)+4), \ \ \ n\ge 7,$$ $$m_3(n) = (m_1(n-1)+0, \ m_1(n-1)+0), \ \ \ n\ge 7,$$ $$m_4(n) = (m_1(n-1)-1, \ m_1(n-1)-3), \ \ \ n\ge 7.$$

(These were edited/corrected a couple of hours after the first post.)

The (seemingly unique) map that realizes $m_1(n)$ is very simple. Here is an attempt at a rendering.

The map shown has 10 regions, 8 in the rim of the wheel, the region with the label $a$, and the unbounded region. The generalization to $n$ regions should be obvious. Such maps do have $m_1(n)$ different 4-colorings with $m_1(n)$ as given above. (Note: 4-colorings include 3-colorings which accounts for the different treatment of odd and even $n$ for $m_1(n)$ and partly accounts for the difference in the other $m_i(n)$.)

Maps that realize the other values are (among perhaps others) minor variations of the map pictured above.

I have tried very hard to catch typos, especially in the formulas given above. Those that love to compute can see if any have slipped by.

Thank you for any information.

-

You've probably done this already, but here are the exact numbers obtained just by counting the 4-colourings over all plane triangulations: each line gives $m_1$, $m_2$, $m_3$, $m_4$

9 regions: 21, 16, 12, 9

10 regions: 44, 28, 21, 20

11 regions: 85, 48, 44, 41

12 regions: 172, 92, 85, 84

13 regions: 341, 176, 172, 169

14 regions: 684, 348, 341, 340

15 regions: 1365, 688, 684, 681

All of these values are uniquely realised, and all fit your formulas.

I would be reasonably confident that this is not known to this level of precision. On the other hand, most people who have thought about this would quickly arrive at the conclusion that the biwheel (the dual of your picture) is the one with the maximum number of vertex 4-colourings.

-
Thanks for the vote of confidence and the references on your web page (plantri, e.g.). (Your link to "planar graphs" is broken b.t.w.) We are new to this and still getting used to things. For example, it is not clear to me why the biwheel should be the triangulation with the max number of colorings. (proof?) Our algorithms were clearly less efficient and only handled up to 12 regions. What caught our attention was the gap between the two top numbers. Since you seem to "collect" these things, email me if you want the other graphs. Web page is in my profile. –  Matt Brin Aug 15 '12 at 4:30
I probably spoke too quickly; while the evidence clearly implies that the biwheel has the most colourings, it is not immediately obvious how to prove it. –  Gordon Royle Aug 17 '12 at 8:38