login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A335203 a(n) is the packing chromatic number of n-hypercube graph. 0
2, 3, 5, 7, 15, 25, 49, 95 (list; graph; refs; listen; history; text; internal format)
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 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

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

P. Torres, 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^ceil(log2(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

Adjacent sequences:  A335200 A335201 A335202 * A335204 A335205 A335206

KEYWORD

nonn,hard,more

AUTHOR

Sergey Kirgizov, May 26 2020

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 8 09:16 EDT 2020. Contains 336293 sequences. (Running on oeis4.)