I brought this up in January, but now know more and can be more precise.
I will have two questions.
How much of this is known?
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.
