

A088202


Chromatic number of the n X n queen graph.


2



1, 4, 5, 5, 5, 7, 7, 9, 10, 11, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26
(list;
graph;
refs;
listen;
history;
text;
internal format)



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

Table of n, a(n) for n=1..26.
F. J. Aragón Artacho, R. Campoy, V. Elser, An enhanced formulation for solving graph coloring problems with the DouglasRachford 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 60coloring of the 60 X 60 queen graph
V. Chvatal, A 60coloring of the 60 X 60 queen graph [Cached copy, pdf version only, with permission]
Jessica Gonzalez and N. J. A. Sloane, Illustration for a(3)=a(4)=a(5)=5
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. 278287
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 np rows and columns.


EXAMPLE

A 10coloring 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

Cf. A275645.
Sequence in context: A144192 A029909 A141276 * A238187 A307109 A046780
Adjacent sequences: A088199 A088200 A088201 * A088203 A088204 A088205


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



