[seqfan] Re: n x n matrices with adjacent entries differing by +/- 1

[Edwin Clark]

On Sun, 2 Nov 2008, Edwin Clark wrote:

>
> Très bien, Benoît! Of course one needs to do a little work to see that the 
> mapping A -> A mod 3 is a surjection as well as an injection.
>
> The same argument should work if we consider any connected graph instead
> the  n by n grid graph which corresponds to the matrix case. That is, the 
> number of 3 colorings of a connected graph with the color of one vertex fixed 
> is the same as the number of ways to label the vertices with integers
> so that one vertex is 0 and the labels for adjacent vertices differ by +/- 1.
> Sounds like something that graph theorists should be aware of.


I retract that statement for an arbitrary graph. There is something else 
going on. Consider a three cycle C(3). C(3) has 6 3-colorings, but there 
is no way to label the vertices with integers so that adjacent vertices 
differ by +/- 1.

--Edwin