OFFSET
1,2
COMMENTS
a(27) is the first open case.
REFERENCES
M. Gardner, The Unexpected Hanging and Other Mathematical Diversions. Simon and Schuster, NY, 1969, p. 191.
Thorold Gosset, Mess. Math., 44 (1914), 48. (Shows a(8) > 8.)
LINKS
F. J. Aragón Artacho, R. Campoy, V. Elser, An enhanced formulation for solving graph coloring problems with the Douglas-Rachford algorithm, arXiv:1808.01022 [math.OC], 2018.
V. Chvatal, Coloring the queen graph
V. Chvatal, Coloring the queen graph [Cached copy, pdf version only, with permission]
V. Chvatal, A 60-coloring of the 60 X 60 queen graph
V. Chvatal, A 60-coloring of the 60 X 60 queen graph [Cached copy, pdf version only, with permission]
John D. Cook, Coloring the queen's graph.
Jessica Gonzalez and N. J. A. Sloane, Illustration for a(3)=a(4)=a(5)=5
M. R. Iyer and V. V. Menon, On Coloring the n × n Chessboard, The American Mathematical Monthly, vol. 73, no. 7, 1966, pp. 721-25.
Witold Jarnicki, W. Myrvold, P. Saltzman, S. Wagon, Properties, Proved and Conjectured, of Keller, Mycielski, and Queen Graphs, arXiv preprint arXiv:1606.07918 [math.CO], 2016.
Stan Wagon, Graph Theory Problems from Hexagonal and Traditional Chess, The College Mathematics Journal, Vol. 45, No. 4, September 2014, pp. 278-287
Eric Weisstein's World of Mathematics, Chromatic Number
Eric Weisstein's World of Mathematics, Queen Graph
FORMULA
Sequence is monotonic and a(n) = n if n is a prime > 3.
a(n) = n if n == 1 or 5 (mod 6).
a(n) <= p := nextprime(n), since we can simply take a solution for p and remove the last n-p rows and columns.
EXAMPLE
A 10-coloring of the 9 X 9 chessboard, showing that a(9) <= 10:
.
0 2 1 7 3 9 5 8 6
1 3 4 5 0 8 6 9 2
2 0 6 8 4 3 1 5 7
3 1 7 9 5 2 4 6 0
4 6 3 2 7 0 8 1 9
5 7 9 4 6 1 3 0 8
6 4 0 1 9 5 2 7 3
7 5 8 3 2 6 9 4 1
8 9 2 6 1 4 0 3 5
CROSSREFS
KEYWORD
nonn,more,hard
AUTHOR
Willem Haemers (Haemers(AT)uvt.nl), Nov 03 2003
EXTENSIONS
Entry revised Mar 22 2004 using material from the Chvatal web site.
a(26)=26 added from the Chvatal web site by N. J. A. Sloane, Aug 10 2016
STATUS
approved