MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This is a redo of my earlier question.

I'm trying again with more precision. I ignored one of the dicta in the "how to ask" page.

For a fixed $n$, what is known (references preferred) about the maximum number of edge 3-colorings (yes, I known the title says (vertex) 4 colorings, but it reduces to the same question) among the following graphs: Planar, simplicial (two vertices have at most one edge between them and there are no 1-gons), triangulations with $n$ vertices so that every loop of three edges bounds a triangle. In the count, it would be best to mod out by the action of $S_3$ on the colors.

I know this number is on the order of $2^{n-4}$. I am looking for references on work on getting exact values. If f(n) is the number, then what is known about the integer sequence f(n).

The considered triangulations have Hamiltonian circuits [Whitney, Ann. of Math. 32 (1931), 378-390]. The restriction that two vertices cannot have two edges between them is not only a hypothesis of Whitney's theorem, but it also rules out a reduction of a given triangulation to a "gluing" of two triangulations giving the number of colorings as a product of the numbers for the two "glued" triangulations.

share|cite|improve this question
Sorry I'm a bit confused. Are you referring to edge colourings of the dual cubic graph perhaps? – Brendan McKay Jan 7 '12 at 10:45
Another gap in my precision is exposed. An edge coloring of the cubic graph is required to have different colors around each vertex. I should have specified that, or specified that the edge coloring of the triangulation is required to have different colors around each face, but not necessarily around each vertex. In case it is not obvious, I am not a graph theorist. – Matt Brin Jan 7 '12 at 14:50

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.