Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #66 Jan 31 2024 01:14:00
%S 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
%N Chromatic number of the n X n queen graph.
%C a(27) is the first open case.
%D M. Gardner, The Unexpected Hanging and Other Mathematical Diversions. Simon and Schuster, NY, 1969, p. 191.
%D Thorold Gosset, Mess. Math., 44 (1914), 48. (Shows a(8) > 8.)
%H F. J. Aragón Artacho, R. Campoy, V. Elser, <a href="https://arxiv.org/abs/1808.01022">An enhanced formulation for solving graph coloring problems with the Douglas-Rachford algorithm</a>, arXiv:1808.01022 [math.OC], 2018.
%H V. Chvatal, <a href="http://www.cs.concordia.ca/~chvatal/queengraphs.html">Coloring the queen graph</a>
%H V. Chvatal, <a href="/A088202/a088202.pdf">Coloring the queen graph</a> [Cached copy, pdf version only, with permission]
%H V. Chvatal, <a href="http://www.cs.concordia.ca/~chvatal/queen60.html">A 60-coloring of the 60 X 60 queen graph</a>
%H V. Chvatal, <a href="/A088202/a088202_1.pdf">A 60-coloring of the 60 X 60 queen graph</a> [Cached copy, pdf version only, with permission]
%H John D. Cook, <a href="https://www.johndcook.com/blog/2024/01/30/coloring-the-queens-graph/">Coloring the queen's graph</a>.
%H Jessica Gonzalez and N. J. A. Sloane, <a href="/A088202/a088202.png">Illustration for a(3)=a(4)=a(5)=5</a>
%H M. R. Iyer and V. V. Menon, <a href="https://www.jstor.org/stable/2313979">On Coloring the n × n Chessboard</a>, The American Mathematical Monthly, vol. 73, no. 7, 1966, pp. 721-25.
%H Witold Jarnicki, W. Myrvold, P. Saltzman, S. Wagon, <a href="https://arxiv.org/abs/1606.07918">Properties, Proved and Conjectured, of Keller, Mycielski, and Queen Graphs</a>, arXiv preprint arXiv:1606.07918 [math.CO], 2016.
%H Stan Wagon, <a href="http://www.jstor.org/stable/10.4169/college.math.j.45.4.278">Graph Theory Problems from Hexagonal and Traditional Chess</a>, The College Mathematics Journal, Vol. 45, No. 4, September 2014, pp. 278-287
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/ChromaticNumber.html">Chromatic Number</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/QueenGraph.html">Queen Graph</a>
%F Sequence is monotonic and a(n) = n if n is a prime > 3.
%F a(n) = n if n == 1 or 5 (mod 6).
%F a(n) <= p := nextprime(n), since we can simply take a solution for p and remove the last n-p rows and columns.
%e A 10-coloring of the 9 X 9 chessboard, showing that a(9) <= 10:
%e .
%e 0 2 1 7 3 9 5 8 6
%e 1 3 4 5 0 8 6 9 2
%e 2 0 6 8 4 3 1 5 7
%e 3 1 7 9 5 2 4 6 0
%e 4 6 3 2 7 0 8 1 9
%e 5 7 9 4 6 1 3 0 8
%e 6 4 0 1 9 5 2 7 3
%e 7 5 8 3 2 6 9 4 1
%e 8 9 2 6 1 4 0 3 5
%Y Cf. A275645.
%K nonn,more,hard
%O 1,2
%A Willem Haemers (Haemers(AT)uvt.nl), Nov 03 2003
%E Entry revised Mar 22 2004 using material from the Chvatal web site.
%E a(26)=26 added from the Chvatal web site by _N. J. A. Sloane_, Aug 10 2016