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