A335203 a(n) is the packing chromatic number of n-hypercube graph.

2, 3, 5, 7, 15, 25, 49, 95

Offset: 1

Author

Sergey Kirgizov, May 26 2020

Keywords

• nonn
• hard
• more

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.

Examples

			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
		

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).