Take the 2-minute tour ×

I understand that it is computationally hard to count the 4-colorings of a given graph. See answers to

this question

In a given class of planar graphs (will leave choice of class open) is there a known function f(n) that gives a sharp (or not sharp) upper bound on the maximum number of 4-colorings (modulo permutations of the colors, or not) over all graphs of size n (what constitutes size n left open for now)?

share|improve this question
I was too vague and perhaps even misusing the phrase 4-coloring. My ignorance shows here. Let us stick to valence three graphs and let the 4-colorings refer to the face colorings. Now in the dual triangulation, the 4-colorings refer to vertex colorings. Let the dual triangulation have no repeated edges. In fact let the dual triangulation be subject to Whitney's theorem and have a Hamiltonian circuit (and sill have no repeated edges). So we do have two triangulated n-gons glued along the boundaries. Is there anything known (references?) about this more restricted setting? –  Matt Brin Jan 6 '12 at 17:04

3 Answers 3

Consider the class of planar triangulations (allowing multi-edges). These are maximal planar graphs (for a fixed number of vertices), i.e. any planar graph can be completed to one. Then the maximal number of 4-colorings of a planar triangulation with $n$ vertices is $3\cdot 2^n$.

To see this, first assume that the triangulation no separating triangle. Whitney proved that any planar triangulation with no separating triangle has a Hamiltonian cycle. On either side of the Hamiltonian cycle, one sees a disk with an $n$-cycle on its boundary, and $n-3$ edges in the interior. The number of colorings of such a graph is $3\cdot 2^n$, since you can color a triangle with $4\cdot 3\cdot 2$ colors, and then the remaining $n-3$ vertices each have $2$ colors available working outwards. So this gives an upper bound on the number of colorings. To achieve this upper bound, take two copies of the triangulated disk, and glue them along the boundary by the identity. Then this is a planar triangulation with the same number of $4$-colorings (of course, there will be many multi-edges, so it is far from simplicial). This class of graphs is a natural class to consider, e.g. in the proof of the $4$-color theorem.

If there is a separating triangle, then one may show that the graph has $<3\cdot 2^n$ $4$-colorings by induction. If a triangulation has a separating triangle, then one may break it up into two triangulations, so that the number of $4$-colorings is the product of the number of colorings of each triangulation $/24$, and by induction one sees that the number of 4-colorings is strictly $<3 \cdot 2^n$.

Maybe you'll object to this choice of graphs, e.g. because of multi-edges. If you make no restriction, then obviously the trivial graph on $n$ vertices will be maximal. For connected graphs, trees will be maximal. Other natural classes are trivalent graphs, bipartite graphs, or simplicial triangulations. I'm not sure about the maximal number of colorings for these classes of graphs.

Addendum: Restricting to $3$-connected simplicial triangulations, the growth is still $O(2^n)$. Consider an $n$-cycle, then the number of $3$-colorings is $O(2^n)$. Then cone it off on both sides to get a simplicial triangulation with $O(2^n)$ $4$-colorings. I'm not sure what the optimal constant is though.

share|improve this answer
Why are planar triangulations Hamiltonian? –  Igor Rivin Jan 6 '12 at 16:35
@ Igor: I forgot the condition about no separating triangles. This was proved by Whitney - see the link in the revision. Thanks. –  Ian Agol Jan 6 '12 at 16:58
@Ian: yes, I know the Whitney theorem (it was used by Dillencourt and Smith to show that any graph whose dual is a four-connected planar triangulation is the one-skeleton of an inscribed convex polyhedron, based on my oevre...) Anyway, I wonder what the sharp upper bound is in general?! –  Igor Rivin Jan 6 '12 at 18:06

This has been studied in the statistical mechanics literature on the antiferromagnetic 4-state Potts model. One place to start reading about recent work from this perspective is the introduction and first few sections of this paper by Salas and Sokal.

One particularly studied family is triangular lattice graphs, which is expected to be an integrable system in some sense of the term.

This structure has led to one result due to Rodney Baxter which I can easily quote here: For graphs with $n$ sites forming a triangular lattice, in the limit of large $n$, the number of 4-colorings is asymptotically $W^n$ where $W=\frac{3\Gamma(1/3)^3}{4\pi^2}\approx 1.46099$.

Jesper Lykke Jacobsen has conjectured formulas for corrections to this due to boundary and corner effects here.

I'm afraid my understanding is not developed enough to write further, but in any case you might write to Alan Sokal or some of the other authors of these papers for their perspective.

share|improve this answer

For every tree on $n$ vertices, there are exactly $4 \times 3^{n-1}$ $4$-colorings. This follows from the fact that its chromatic polynomial is $t(t-1)^{n-1}$.

(Or by induction since every tree with at least one edge has a "leaf.")

share|improve this answer
If one has a forest, one can get closer to $4^n$. Gerhard "Ask Me About System Design" Paseman, 2012.01.06 –  Gerhard Paseman Jan 6 '12 at 19:57

Your Answer


