login
A335203
a(n) is the packing chromatic number of n-hypercube graph.
2
2, 3, 5, 7, 15, 25, 49, 95
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 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.
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 and 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^ceiling(log_2(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
KEYWORD
nonn,hard,more
AUTHOR
Sergey Kirgizov, May 26 2020
STATUS
approved