Timeline for Least number of ways to color a map using at most 4 colors
Current License: CC BY-SA 4.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 28, 2023 at 9:27 | vote | accept | Dr.X | ||
| Oct 28, 2023 at 0:29 | comment | added | Brendan McKay | 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. | |
| Oct 27, 2023 at 17:14 | answer | added | Titwig | timeline score: 0 | |
| Oct 27, 2023 at 12:45 | comment | added | Boris Bukh | 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. | |
| Oct 27, 2023 at 11:54 | comment | added | Gerry Myerson | 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. | |
| Oct 27, 2023 at 11:13 | comment | added | mme | 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$. | |
| Oct 27, 2023 at 10:50 | history | asked | Dr.X | CC BY-SA 4.0 |