A396138 - OEIS

%I #5 May 21 2026 18:45:41

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

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

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

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

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

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

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

%C The hexagonal-lattice analog of A278299.

%H Peter Exley, <a href="https://github.com/pexley-math/oeis-A396138">Solver code, data, and figures</a>, GitHub.

%Y 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).

%K nonn,hard,more

%O 1,2

%A _Peter Exley_, May 18 2026