# Queen's Graph

Gordon Royle gordon at csse.uwa.edu.au
Thu Sep 11 10:45:12 CEST 2003

```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