𝔖 Bobbio Scriptorium
✦   LIBER   ✦

New bounds on a hypercube coloring problem

✍ Scribed by Hung Quang Ngo; Ding-Zhu Du; Ronald L. Graham

Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
57 KB
Volume
84
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

✦ Synopsis

In studying the scalability of optical networks, one problem which arises involves coloring the vertices of the n-cube with as few colors as possible such that any two vertices whose Hamming distance is at most k are colored differently. Determining the exact value of Ο‡ k (n), the minimum number of colors needed, appears to be a difficult problem. In this note, we improve the known lower and upper bounds of Ο‡ k (n) and indicate the connection of this coloring problem to linear codes.

πŸ“œ SIMILAR VOLUMES

New upper bounds on harmonious colorings
New upper bounds on harmonious colorings
✍ Keith Edwards; Colin McDiarmid πŸ“‚ Article πŸ“… 1994 πŸ› John Wiley and Sons 🌐 English βš– 435 KB

## Abstract We present an improved upper bound on the harmonious chromatic number of an arbitrary graph. We also consider β€žfragmentable”︁ classes of graphs (an example is the class of planar graphs) that are, roughly speaking, graphs that can be decomposed into bounded‐sized components by removing

On a leverage problem in the hypercube
On a leverage problem in the hypercube
✍ Peter Hamburger; Raymond E. Pippert; W. Douglas Weakley πŸ“‚ Article πŸ“… 1992 πŸ› John Wiley and Sons 🌐 English βš– 210 KB