|
%I #39 May 23 2022 03:54:04
%S 2,3,5,7,15,25,49,95
%N a(n) is the packing chromatic number of n-hypercube graph.
%C 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 There are no known exact formulas or recurrence relations. Some asymptotic results and bounds are given in the Formula section.
%H 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 W. Goddard, S. M. Hedetniemi, S. T. Hedetniemi, J. M. Harris, and R. F. Rall, <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.140.2341">Broadcast chromatic numbers of graphs</a>, Ars Combinatoria, 86 (2008) 33-49.
%H 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 a(n) ~ (1/2 - O(1/k)) * 2^k (Proposition 7.3 from Goddard et al.).
%F a(n) >= 2*a(n-1) - (n-1) (Corollary 1 from Torres and Valencia-Pabon).
%F 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 Hypercube of dimension 1 needs 2 colors:
%e 1 --- 2
%e Hypercube of dimension 2 needs 3 colors:
%e 1 --- 2
%e | |
%e | |
%e 3 --- 1
%e Hypercube of dimension 3 needs 5 colors:
%e 1 ----------- 2
%e | \ / |
%e | \ / |
%e | 4 --- 1 |
%e | | | |
%e | | | |
%e | 2 --- 5 |
%e | / \ |
%e | / \ |
%e 3 ----------- 1
%K nonn,hard,more
%O 1,1
%A _Sergey Kirgizov_, May 26 2020
|
