The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A335203 a(n) is the packing chromatic number of n-hypercube graph. 0
 2, 3, 5, 7, 15, 25, 49, 95 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,1 COMMENTS 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 a 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. There are no known exact formulas or recurrence relations. Some asymptotic results and bounds are given in the Formula section. LINKS B. Brešar, J. Ferme, S. Klavžar, and D. F. Rall, Survey on packing colorings, Discussiones Mathematicae Graph Theory, to appear (2020). W. Goddard, S. M. Hedetniemi, S. T. Hedetniemi, J. M. Harris, and R. F. Rall, Broadcast chromatic numbers of graphs, Ars Combinatoria, 86 (2008) 33-49. P. Torres, M. Valencia-Pabon, The packing chromatic number of hypercubes, Discrete Applied Mathematics, 190 (2015), 127-140. FORMULA a(n) ~ (1/2 - O(1/k)) * 2^k  (Proposition 7.3 from Goddard et al.). a(n) >= 2*a(n-1) - (n-1) (Corollary 1. from Torres and Valencia-Pabon). a(n) <= 3 + 2^n * (1/2 - 1/(2^ceil(log2(n)))) - 2 * floor((n-4)/2) (Thm. 1 from Torres and Valencia-Pabon). EXAMPLE Hypercube of dimension 1 needs 2 colors:   1 --- 2 Hypercube of dimension 2 needs 3 colors:   1 --- 2   |     |   |     |   3 --- 1 Hypercube of dimension 3 needs 5 colors:   1 ----------- 2   | \         / |   |  \       /  |   |   4 --- 1   |   |   |     |   |   |   |     |   |   |   2 --- 5   |   |  /       \  |   | /         \ |   3 ----------- 1 CROSSREFS Sequence in context: A157833 A175758 A151531 * A079987 A085547 A058702 Adjacent sequences:  A335200 A335201 A335202 * A335204 A335205 A335206 KEYWORD nonn,hard,more AUTHOR Sergey Kirgizov, May 26 2020 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified August 8 09:16 EDT 2020. Contains 336293 sequences. (Running on oeis4.)