login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 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]

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 21 22:47 EDT 2021. Contains 348160 sequences. (Running on oeis4.)