2
$\begingroup$

Given all the maps with k regions, consider the map(s) that can be colored in the least amount of possible ways. In how many ways can it be colored (n)? (using at most 4 colors and not counting different permutations of the colors.)

Is there an integer sequence? I couldn't find it. I must have missed it.

Here is a map with 4 regions that can only be colored in one way.

map with 4 regions

And here is one with 5 regions, only one way to color it.

map with 5 regions

The sequence goes like this:

1,1,1,1,1,...

I don't know the answer for a map with 6 regions.

Improve this question
$\endgroup$
4
  • 6
    $\begingroup$ Let's focus on the planar dual graph. Your graphs $G_n$ have the property that each face is a triangle, and $G_n$ has a unique coloring (up to relabeling colors). Now form $G_{n+1}$ by taking one of the triangular regions and subdividing it by placing a vertex in the center. You already know there's only one coloring on $G_n$ up to permutation; now the color on the new vertex is forced on you, so there's only $1$ coloring of $G_{n+1}$. This is in fact exactly what you did in passing from $G_4$ to $G_5$. $\endgroup$
    – mme
    Commented Oct 27, 2023 at 11:13
  • 1
    $\begingroup$ All those graphs have chromatic polynomial $k(k-1)(k-2)(k-3)^{n-4}$, which evaluates to $24$ at $k=4$; but those are just the $24$ permutations of the colors, so essentially just one way to color. $\endgroup$
    – Gerry Myerson
    Commented Oct 27, 2023 at 11:54
  • 1
    $\begingroup$ This does not answer your question, but it is known that there are exponentially many $5$-list colorings of planar graphs. There are also other related results. $\endgroup$
    – Boris Bukh
    Commented Oct 27, 2023 at 12:45
  • 3
    $\begingroup$ The graphs defined by mme are sometimes called Apollonian graphs and are uniquely the only class of simple planar graph with exactly one 4-colouring (up to exchange of colours). See the Wikipedia article "Apollonian network". Note that they all contain a vertex of degree 3 (the last one added) so the question remains of what is the least number of colourings when the minimum degree is 4 or 5. Probably this has been studied. $\endgroup$
    – Brendan McKay
    Commented Oct 28, 2023 at 0:29

1 Answer 1

Reset to default
0
$\begingroup$

Here is one with 6 regions, only one way to color it (F in red sorry for the quality) :

enter image description here

Improve this answer
$\endgroup$
1
  • 4
    $\begingroup$ This is the same example as mme gave in a comment. $\endgroup$
    – Brendan McKay
    Commented Oct 28, 2023 at 0:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .