

A335203


a(n) is the packing chromatic number of nhypercube graph.


0




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 ndimensional 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

Table of n, a(n) for n=1..8.
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) 3349.
P. Torres, M. ValenciaPabon, The packing chromatic number of hypercubes, Discrete Applied Mathematics, 190 (2015), 127140.


FORMULA

a(n) ~ (1/2  O(1/k)) * 2^k (Proposition 7.3 from Goddard et al.).
a(n) >= 2*a(n1)  (n1) (Corollary 1. from Torres and ValenciaPabon).
a(n) <= 3 + 2^n * (1/2  1/(2^ceil(log2(n))))  2 * floor((n4)/2) (Thm. 1 from Torres and ValenciaPabon).


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



