|
| |
|
|
A335203
|
|
a(n) is the packing chromatic number of n-hypercube graph.
|
|
2
|
| |
|
|
|
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).
|
|
|
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
|
|
|
|
KEYWORD
|
nonn,hard,more
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
