On reflection, a modicum of signposting might be in order: so note that colourings (of either class) number (2 or 3 times) T(m, n) = O(1+d)^(m n) . Note also that the Maple counting program given under A078099 requires substantial editing, and is impracticably slow for m > 8 . Results from a more elaborate Magma program can be made available, should anyone feel sufficiently motivated to demand them ... Fred Lunnon On 1/9/14, Fred Lunnon <fred.lunnon@gmail.com> wrote:
Within the (exiguous) bowels of OEIS A078099 there lurks a throwaway comment to the effect that 3-colouring the nodes of a m x n grid such that edge-adjacent pairs of nodes are assigned distinct colours is equivalent to 2-colouring the nodes such that no square (4-circuit) has both diagonals assigned distinct colours. [Establishing this equivalence is not entirely trivial.] In default of any earlier attribution, I propose to dub the latter colourings "Hardin" colourings.
Though I haven't sat down to prove it, it seems reasonable to assume that as n,m -> oo the density of diagonal pairs with equal colours approaches a limit d , for a `random' Hardin colouring. [We can just sum frequencies over distinct n x n colourings where n is large, then take means.]
I can show d > 0.5382 , and extrapolation suggests d ~ 0.5395 +/- 0.00005 ; can anybody improve on these values, find an explicit expression, or show a non-trivial upper bound for d ?
Fred Lunnon