Queen's Graph

[Gordon Royle]

Hi Seqfans..

This subject arose in GRAPHNET, which I am sure some of you also subscribe
to, but I think it is of interest to sequence fans..

Vasek Chvatal raised the (old) question of considering the number of colours
needed to colour the n x n "queen's graph" - the graph with vertex set equal
to the cells on a chessboard, with two vertices adjacent if a queen can move
from one to the other.

Clearly, as each row/column is an n-clique, this graph needs at least n
colours.

And in fact, when n congruent to 1,5 mod 6 it can be shown that n colours
suffices - denote this by (*).

For small values of n, we have

    n=3    5 colours
    n=4    5 colours
    n=5    5 colours (*)
    n=6    7 colours
    n=7    7 colours (*)
    n=8    9 colours
    n=9    10 colours
    n=10    11 colours
    n=11     11 colours (*)

But then Guenter Stertenbrink supplied a 12-colouring of the 12x12 queens
graph

    n = 12    12 colours
    n = 13    13 colours (*)

Although there are many queen-related sequences in the OEIS, I cannot find
this one... so will add it in a few days after asking for any further
information and/or comments....

Cheers

gordon