New bounds on a hypercube coloring problem.
type: Item
instance of: scholarly article
title: New bounds on a hypercube coloring problem.
zbMATH Open document ID: 1042.68083
DOI: 10.1016/S0020-0190(02)00301-0
author: Du Ding-Zhu
author: Ron Graham
author: Hung Q. Ngo
published in: Information Processing Letters
publication date: 2003-01-21T00:00:00Z
review text: 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 \(\chi_{\overline{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 \(\chi_{\overline{k}}(n)\) and indicate the connection of this coloring problem to linear codes.
Mathematics Subject Classification ID: 68R05
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1856486
zbMATH Keywords: Combinatorial problems
zbMATH Keywords: cube
zbMATH Keywords: Coloring
MaRDI profile type: Publication
cites work: A coloring problem on the \(n\)-cube
cites work: Q4004140
cites work: Near-optimal conflict-free channel set assignments for an optical cluster-based hypercube network
full work available at URL: s0020-0190(02)00301-0
OpenAlex ID: W2100597435
description: scientific article; zbMATH DE number 1856486