A335203 -id:A335203 - cp's OEIS frontend

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

1, 3, 4, 5, 7, 8, 9, 9, 10, 11

Offset: 1

Robert C. Lyons, Apr 25 2023

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.
The sequence converges to 15, because the packing chromatic number of the infinite square grid is 15. See links.
a(11) <= 12, a(12) <= 12, a(13) <= 13, a(14) <= 13 and a(15) <= 14. - Martin Ehrenstein, May 01 2023

			In the following 2 X 2 grid, the maximum value is 3, and the distance between the two cells containing 1 is 2:
 1 2
 3 1
In the following 3 X 3 grid, the maximum value is 4, and the distance between the two cells containing 3 is 4:
 2 1 3
 1 4 1
 3 1 2
In the following 4 X 4 grid, the maximum value is 5, and the distance between each pair of cells containing 3 is 4:
 1 2 1 3
 3 1 4 1
 1 5 1 2
 2 1 3 1
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:
 1 2 1 3 1
 3 1 4 1 2
 1 5 1 6 1
 2 1 7 1 3
 1 3 1 2 1
In the following 6 X 6 grid, the maximum value is 8, and the distance between the two cells containing 5 is 6:
 1 2 1 3 1 2
 3 1 4 1 5 1
 1 6 1 2 1 3
 2 1 3 1 7 1
 1 5 1 8 1 2
 3 1 2 1 3 1
In the following 7 X 7 grid, the maximum value is 9, and the distance between the two cells containing 7 is 8:
 1 2 1 3 1 2 1
 3 1 4 1 5 1 3
 1 6 1 2 1 7 1
 2 1 3 1 8 1 2
 1 5 1 9 1 3 1
 3 1 2 1 4 1 5
 1 7 1 3 1 2 1
In the following 8 X 8 grid, the maximum value is 9, and the distance between the two cells containing 7 is 8:
 1 2 1 3 1 2 1 3
 3 1 4 1 5 1 6 1
 1 7 1 2 1 3 1 2
 2 1 3 1 8 1 4 1
 1 5 1 9 1 2 1 3
 3 1 2 1 3 1 7 1
 1 6 1 4 1 5 1 2
 2 1 3 1 2 1 3 6

Martin Ehrenstein, Example grids illustrating terms and bounds for n = 9..16
Wayne Goddard, Sandra M. Hedetniemi, Stephen T. Hedetniemi, John M. Harris, and Douglas F. Rall, Broadcast Chromatic Numbers of Graphs, Ars Combinatoria, 86 (2008), 33-49.
Kevin Hartnett, The Number 15 Describes the Secret Limit of an Infinite Grid, Quanta Magazine, Apr 20 2023.
Robert C. Lyons, Python program that calculates the sequence.
Bernardo Subercaseaux and Marijn J. H. Heule, The Packing Chromatic Number of the Infinite Square Grid is 15, arXiv:2301.09757 [cs.DM], 2023.

Cf. A335203.

Python
```
# See link.
```

a(9)-a(10) from Martin Ehrenstein, May 01 2023

A363043 Triangle read by rows: T(n,k) is the number of unlabeled graphs with n nodes and packing chromatic number k, 1 <= k <= n.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 4, 5, 1, 1, 6, 15, 11, 1, 1, 10, 42, 73, 29, 1, 1, 14, 109, 390, 439, 90, 1, 1, 21, 278, 1953, 5546, 4188, 358, 1, 1, 29, 687, 9085, 61023, 134183, 67888, 1771, 1, 1, 41, 1694, 40344, 572235, 3517101, 5860434, 2001582, 11735, 1

Offset: 1

Pontus von Brömssen, May 14 2023

The concept of the packing chromatic number was introduced by Goddard et al. (2008) under the name broadcast chromatic number. The term packing chromatic number was introduced by Brešar et al. (2007).

			Triangle begins:
  n\k| 1  2    3     4      5       6       7       8     9 10
  ---+--------------------------------------------------------
   1 | 1
   2 | 1  1
   3 | 1  2    1
   4 | 1  4    5     1
   5 | 1  6   15    11      1
   6 | 1 10   42    73     29       1
   7 | 1 14  109   390    439      90       1
   8 | 1 21  278  1953   5546    4188     358       1
   9 | 1 29  687  9085  61023  134183   67888    1771     1
  10 | 1 41 1694 40344 572235 3517101 5860434 2001582 11735  1

Boštjan Brešar, Sandi Klavžar, and Douglas F. Rall, On the packing chromatic number of Cartesian products, hexagonal lattice, and trees, Discrete Applied Mathematics 155 (2007), 2303-2311.
Wayne Goddard, Sandra M. Hedetniemi, Stephen T. Hedetniemi, John M. Harris, and Douglas F. Rall, Broadcast chromatic numbers of graphs, Ars Combinatoria 86 (2008), 33-49.

Cf. A000041, A000088 (row sums), A084268 (chromatic number), A275622 (cubic graphs), A335203 (hypercube graph) A362580 (square grid graph), A363044 (connected).

T(n,1) = 1. (The only graphs with packing chromatic number 1 are the graphs with no edges.)
T(n,2) = A000041(n)-1. (The only graphs with packing chromatic number 2 are those consisting of star graph components, with at least one of the components containing more than one node.)
T(n,n) = 1. (The only graph with n nodes and packing chromatic number n is the complete graph on n nodes.)

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Extensions