A335203 - OEIS

%I #41 Aug 06 2024 11:19:50

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

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

%C 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.

%C There are no known exact formulas or recurrence relations. Some asymptotic results and bounds are given in the Formula section.

%H B. Brešar, J. Ferme, S. Klavžar, and D. F. Rall, <a href="https://www.fmf.uni-lj.si/~klavzar/preprints/DMGT-2320.pdf">Survey on packing colorings</a>, Discussiones Mathematicae Graph Theory, to appear (2020).

%H W. Goddard, S. M. Hedetniemi, S. T. Hedetniemi, J. M. Harris, and R. F. Rall, <a href="https://citeseerx.ist.psu.edu/pdf/cb49fdb6d2e83c09b4f9a295ed966c6785c2928b">Broadcast chromatic numbers of graphs</a>, Ars Combinatoria, 86 (2008) 33-49.

%H P. Torres and M. Valencia-Pabon, <a href="https://hal.archives-ouvertes.fr/hal-00926875">The packing chromatic number of hypercubes</a>, Discrete Applied Mathematics, 190 (2015), 127-140.

%F a(n) ~ (1/2 - O(1/k)) * 2^k  (Proposition 7.3 from Goddard et al.).

%F a(n) >= 2*a(n-1) - (n-1) (Corollary 1 from Torres and Valencia-Pabon).

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

%e Hypercube of dimension 1 needs 2 colors:

%e   1 --- 2

%e Hypercube of dimension 2 needs 3 colors:

%e   1 --- 2

%e   |     |

%e   |     |

%e   3 --- 1

%e Hypercube of dimension 3 needs 5 colors:

%e   1 ----------- 2

%e   | \         / |

%e   |  \       /  |

%e   |   4 --- 1   |

%e   |   |     |   |

%e   |   |     |   |

%e   |   2 --- 5   |

%e   |  /       \  |

%e   | /         \ |

%e   3 ----------- 1

%K nonn,hard,more

%O 1,1

%A _Sergey Kirgizov_, May 26 2020