A088202 Chromatic number of the n X n queen graph.

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

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

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