cp's OEIS Frontend

A362580 a(n) = packing chromatic number of an n X n grid.

%I A362580 #33 May 01 2023 10:00:49
%S A362580 1,3,4,5,7,8,9,9,10,11
%N A362580 a(n) = packing chromatic number of an n X n grid.
%C A362580 a(n) is the minimum k such that an n X n grid can be colored with positive integers less than or equal to k, and the taxicab distance between each pair of cells containing the same value v is greater than v.
%C A362580 The sequence converges to 15, because the packing chromatic number of the infinite square grid is 15. See links.
%C A362580 a(11) <= 12, a(12) <= 12, a(13) <= 13, a(14) <= 13 and a(15) <= 14. - _Martin Ehrenstein_, May 01 2023
%H A362580 Martin Ehrenstein, <a href="/A362580/a362580.txt">Example grids illustrating terms and bounds for n = 9..16</a>
%H A362580 Wayne Goddard, Sandra M. Hedetniemi, Stephen T. Hedetniemi, John M. Harris, and Douglas F. Rall, <a href="https://www.researchgate.net/publication/220620011_Braodcast_Chromatic_Numbers_of_Graphs">Broadcast Chromatic Numbers of Graphs</a>, Ars Combinatoria, 86 (2008), 33-49.
%H A362580 Kevin Hartnett, <a href="https://www.quantamagazine.org/the-number-15-describes-the-secret-limit-of-an-infinite-grid-20230420/">The Number 15 Describes the Secret Limit of an Infinite Grid</a>, Quanta Magazine, Apr 20 2023.
%H A362580 Robert C. Lyons, <a href="/A362580/a362580.py.txt">Python program that calculates the sequence</a>.
%H A362580 Bernardo Subercaseaux and Marijn J. H. Heule, <a href="https://arxiv.org/abs/2301.09757">The Packing Chromatic Number of the Infinite Square Grid is 15</a>, arXiv:2301.09757 [cs.DM], 2023.
%e A362580 In the following 2 X 2 grid, the maximum value is 3, and the distance between the two cells containing 1 is 2:
%e A362580  1 2
%e A362580  3 1
%e A362580 In the following 3 X 3 grid, the maximum value is 4, and the distance between the two cells containing 3 is 4:
%e A362580  2 1 3
%e A362580  1 4 1
%e A362580  3 1 2
%e A362580 In the following 4 X 4 grid, the maximum value is 5, and the distance between each pair of cells containing 3 is 4:
%e A362580  1 2 1 3
%e A362580  3 1 4 1
%e A362580  1 5 1 2
%e A362580  2 1 3 1
%e A362580 In the following 5 X 5 grid, the maximum value is 7, and the distance between each pair of cells containing 3 is greater than 3:
%e A362580  1 2 1 3 1
%e A362580  3 1 4 1 2
%e A362580  1 5 1 6 1
%e A362580  2 1 7 1 3
%e A362580  1 3 1 2 1
%e A362580 In the following 6 X 6 grid, the maximum value is 8, and the distance between the two cells containing 5 is 6:
%e A362580  1 2 1 3 1 2
%e A362580  3 1 4 1 5 1
%e A362580  1 6 1 2 1 3
%e A362580  2 1 3 1 7 1
%e A362580  1 5 1 8 1 2
%e A362580  3 1 2 1 3 1
%e A362580 In the following 7 X 7 grid, the maximum value is 9, and the distance between the two cells containing 7 is 8:
%e A362580  1 2 1 3 1 2 1
%e A362580  3 1 4 1 5 1 3
%e A362580  1 6 1 2 1 7 1
%e A362580  2 1 3 1 8 1 2
%e A362580  1 5 1 9 1 3 1
%e A362580  3 1 2 1 4 1 5
%e A362580  1 7 1 3 1 2 1
%e A362580 In the following 8 X 8 grid, the maximum value is 9, and the distance between the two cells containing 7 is 8:
%e A362580  1 2 1 3 1 2 1 3
%e A362580  3 1 4 1 5 1 6 1
%e A362580  1 7 1 2 1 3 1 2
%e A362580  2 1 3 1 8 1 4 1
%e A362580  1 5 1 9 1 2 1 3
%e A362580  3 1 2 1 3 1 7 1
%e A362580  1 6 1 4 1 5 1 2
%e A362580  2 1 3 1 2 1 3 6
%o A362580 (Python) # See link.
%Y A362580 Cf. A335203.
%K A362580 nonn,hard,more
%O A362580 1,2
%A A362580 _Robert C. Lyons_, Apr 25 2023
%E A362580 a(9)-a(10) from _Martin Ehrenstein_, May 01 2023