cp's OEIS Frontend

A335203 a(n) is the packing chromatic number of n-hypercube graph.

%I A335203 #41 Aug 06 2024 11:19:50
%S A335203 2,3,5,7,15,25,49,95
%N A335203 a(n) is the packing chromatic number of n-hypercube graph.
%C A335203 A packing coloring of a graph associates an integer color to every graph vertex in such a way that for any k > 0 if two different vertices share the same color k, they must be at distance at least k+1. a(n) is the minimal number of colors (1,2,3,...) needed to perform a packing coloration of an n-dimensional hypercube graph. Only the first terms, up to n = 8, are known. In contrast, the ordinary chromatic number of any hypercube is always equals 2, since any hypercube is a bipartite graph.
%C A335203 There are no known exact formulas or recurrence relations. Some asymptotic results and bounds are given in the Formula section.
%H A335203 B. Brešar, J. Ferme, S. Klavžar, and D. F. Rall, <a href="https://www.fmf.uni-lj.si/~klavzar/preprints/DMGT-2320.pdf">Survey on packing colorings</a>, Discussiones Mathematicae Graph Theory, to appear (2020).
%H A335203 W. Goddard, S. M. Hedetniemi, S. T. Hedetniemi, J. M. Harris, and R. F. Rall, <a href="https://citeseerx.ist.psu.edu/pdf/cb49fdb6d2e83c09b4f9a295ed966c6785c2928b">Broadcast chromatic numbers of graphs</a>, Ars Combinatoria, 86 (2008) 33-49.
%H A335203 P. Torres and M. Valencia-Pabon, <a href="https://hal.archives-ouvertes.fr/hal-00926875">The packing chromatic number of hypercubes</a>, Discrete Applied Mathematics, 190 (2015), 127-140.
%F A335203 a(n) ~ (1/2 - O(1/k)) * 2^k  (Proposition 7.3 from Goddard et al.).
%F A335203 a(n) >= 2*a(n-1) - (n-1) (Corollary 1 from Torres and Valencia-Pabon).
%F A335203 a(n) <= 3 + 2^n * (1/2 - 1/(2^ceiling(log_2(n)))) - 2 * floor((n-4)/2) (Thm. 1 from Torres and Valencia-Pabon).
%e A335203 Hypercube of dimension 1 needs 2 colors:
%e A335203   1 --- 2
%e A335203 Hypercube of dimension 2 needs 3 colors:
%e A335203   1 --- 2
%e A335203   |     |
%e A335203   |     |
%e A335203   3 --- 1
%e A335203 Hypercube of dimension 3 needs 5 colors:
%e A335203   1 ----------- 2
%e A335203   | \         / |
%e A335203   |  \       /  |
%e A335203   |   4 --- 1   |
%e A335203   |   |     |   |
%e A335203   |   |     |   |
%e A335203   |   2 --- 5   |
%e A335203   |  /       \  |
%e A335203   | /         \ |
%e A335203   3 ----------- 1
%K A335203 nonn,hard,more
%O A335203 1,1
%A A335203 _Sergey Kirgizov_, May 26 2020