[seqfan] Re: n x n matrices with adjacent entries differing by +/- 1
eclark at math.usf.edu
Sun Nov 2 19:27:32 CET 2008
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.
More information about the SeqFan