A396138 Minimum number of cells in a connected polyhex that admits an n-coloring such that every unordered pair of distinct colors shares at least one edge.

1, 2, 3, 5, 7, 9, 12, 16, 18, 21

Offset

1,2

Comments

This is a complete-coloring (achromatic-type) problem: the coloring need not be proper, so two edge-adjacent cells may share a color; a valid n-coloring is one in which all binomial(n,2) color pairs occur on some cell-cell edge.

Two lower bounds hold, where k denotes the number of cells:

- Edge-isoperimetric bound L1(n) = min { k : 3*k - ceiling(sqrt(12*k - 3)) >= binomial(n, 2) }.

- Per-color bound L2(n) = n * ceiling((n - 1) / 6).

Their maximum equals a(n) for all n in 1..10 except n = 7, where a(7) = 12 exceeds it by one.

The hexagonal-lattice analog of A278299.

Links

Table of n, a(n) for n=1..10.

Peter Exley, Solver code, data, and figures, GitHub.

Crossrefs

Cf. A000228 (number of free polyhexes with n cells), A001207 (number of fixed polyhexes with n cells), A135711 (minimal perimeter of a polyhex with n cells), A278299 (smallest polyomino with the same coloring property on the square grid).

Sequence in context: A133231 A235111 A228896 * A281783 A224854 A074752

Adjacent sequences: A396134 A396135 A396137 * A396139 A396140 A396141

Keyword

nonn,hard,more

Author

Peter Exley, May 18 2026

Status

approved