VOOZH about

URL: https://oeis.org/A278299

⇱ A278299 - OEIS

login
A278299
a(n) is the tile count of the smallest polyomino with an n-coloring such that every color is adjacent to every other distinct color at least once.
1
2, 4, 6, 9, 12, 15, 19, 24, 30, 34, 40, 46, 56, 61, 69, 77, 90, 96, 106
OFFSET
2,1
COMMENTS
Only edge-to-edge adjacencies are considered.
The sequence is bounded above by A053439(n-1).
a(n) is bounded below by n * ceiling((n - 1)/4). This bound is achieved for n=2, n=6, and n=10.
From Peter Exley, Mar 22 2026: (Start)
Lower bound: a(n) >= max(floor((n^2+n+5)/4), n*ceiling((n-1)/4)). The first term (edge bound) counts minimum internal edges needed; the second (contact bound) counts minimum cells per color.
For n == 2 (mod 4), a(n) = n*ceiling((n-1)/4) (contact bound is tight). Proved for n = 2, 6, 10, 14, 18.
For n == 0 (mod 4) with n <= 16, a(n) = floor((n^2+n+5)/4) (edge bound is tight). Proved for n = 4, 8, 12, 16.
This sequence is the inverse of the achromatic number problem for grid subgraphs: a(n) = min |V(H)| over connected subgraphs H of the infinite grid with achromatic number psi(H) >= n.
a(13) improved from upper bound 47 to proved value 46, a(17) from 78 to 77. (End)
116 <= a(21) <= 117, a(22)=132, 139 <= a(23) <= 141, 151 <= a(24) <= 154, 163 <= a(25) <= 168, a(26)=182, 190 <= a(27) <= 195. - Nels Buhrley, Mar 28 2026
a(25) upper bound improved to 167. Found new upper bounds: a(28) <= 208, a(29) <= 224 and a(30) <= 240. - Dmitry Kamenetsky, Apr 02 2026
EXAMPLE
Example: for n = 4, the following diagram gives a minimal polyomino of a(4) = 6 tiles:
+---+---+
| 1 | 4 |
+---+---+---+
| 4 | 3 | 2 |
+---+---+---+
| 1 |
+---+
Example: for n = 10, the following diagram gives a minimal polyomino of a(10) = 30 tiles. Note that redundant adjacencies, e.g., between 2 and 7, can exist in minimal diagrams.
+---+---+
| 8 | 6 |
+---+---+---+---+---+
| 3 | 2 | 5 | 9 | 4 |
+---+---+---+---+---+---+---+---+
| 2 | 7 | 5 | 1 | 4 | 2 | 10| 9 |
+---+---+---+---+---+---+---+---+
| 6 | 9 | 8 | 3 | 6 | 7 | 8 | 1 |
+---+---+---+---+---+---+---+---+
| 10| 3 | 4 | 7 | 1 | 10| 5 |
+---+---+---+---+---+---+---+
From Ryan Lee, May 14 2019: (Start)
Example for n = 11:
+---+---+---+---+---+
| 9 | 11| 2 | 5 | 8 |
+---+---+---+---+---+---+
| 1 | 5 | 10| 9 | 2 | 1 |
+---+---+---+---+---+---+
| 4 | 6 | 11| 8 | 7 | 3 |
+---+---+---+---+---+---+
| 3 | 9 | 7 | 10| 6 | 2 |
+---+---+---+---+---+---+
| 11| 4 | 5 | 3 | 8 | 4 |
+---+---+---+---+---+---+
| 1 | 10| | 6 | 1 | 7 |
+---+---+ +---+---+---+
(End)
From Peter Exley, Mar 22 2026: (Start)
a(13) = 46:
+---+---+---+---+---+
| 1 | 10| 12| 13| 10|
+---+---+---+---+---+---+---+
| 9 | 6 | 2 | 1 | 4 | 3 | 12|
+---+---+---+---+---+---+---+
| 1 | 3 | 13| 7 | 12| 2 | 8 |
+---+---+---+---+---+---+---+
| 13| 11| 6 | 10| 5 | 4 | 11|
+---+---+---+---+---+---+---+
| 9 | 2 | 7 | 4 | 8 | 6 | 12|
+---+---+---+---+---+---+---+
| 11| 5 | 3 | 9 | 7 | 5 | 9 |
+---+---+---+---+---+---+---+
| 13| 8 | 10| 11| 1 | 8 |
+---+---+---+---+---+---+
(End)
From Nels Buhrley and Ryan Lee, Mar 27 2026: (Start)
a(19) = 96:
+---+---+---+---+---+---+---+---+---+---+---+---+
|12 | 1 | 6 | 2 |18 |11 |17 |18 | 9 |13 |16 |18 |
+---+---+---+---+---+---+---+---+---+---+---+---+
|19 |11 | 3 |17 | 6 |10 |12 |13 | 6 |19 | 9 |10 |
+---+---+---+---+---+---+---+---+---+---+---+---+
| 7 | 9 | 2 | 7 | 4 |14 |18 | 7 |12 |14 | 3 |19 |
+---+---+---+---+---+---+---+---+---+---+---+---+
|10 |17 |16 | 8 | 3 | 5 |19 | 1 | 9 |15 |10 | 8 |
+---+---+---+---+---+---+---+---+---+---+---+---+
| 2 |14 | 7 | 6 |15 | 1 |17 |13 |14 | 8 | 4 | 9 |
+---+---+---+---+---+---+---+---+---+---+---+---+
| 4 |11 |15 |16 |19 | 4 | 5 |10 | 1 | 2 |13 | 5 |
+---+---+---+---+---+---+---+---+---+---+---+---+
|17 | 8 |18 | 5 | 2 |15 |12 |16 | 3 |12 |11 | 6 |
+---+---+---+---+---+---+---+---+---+---+---+---+
|15 |13 | 3 | 7 |11 | 5 | 8 | 1 |18 | 4 |16 |14 |
+---+---+---+---+---+---+---+---+---+---+---+---+
(End)
CROSSREFS
Cf. A053439.
Sequence in context: A194203 A261222 A130025 * A145802 A076271 A036441
KEYWORD
nonn,hard,more,changed
AUTHOR
Alec Jones and Peter Kagey, Nov 17 2016
EXTENSIONS
a(11) from Ryan Lee, May 14 2019
a(12)-a(18) from Peter Exley, Mar 22 2026
a(19)-a(20) from Nels Buhrley and Ryan Lee, Mar 27 2026
STATUS
approved