New bounds on a hypercube coloring problem.
From MaRDI portal
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.
Recommendations
Cites work
Cited in
(21)- A distance-labelling problem for hypercubes
- On the acyclic chromatic number of Hamming graphs
- A coloring problem in Hamming spaces
- A coloring problem on the \(n\)-cube
- The robust coloring problem.
- New results on two hypercube coloring problems
- Two coloring problems on matrix graphs
- The \(b\)-chromatic number of powers of hypercube
- Distance Labelling Problems for Hypercubes and Hamming Graphs – A Survey
- On a coloring problem on the n-cube
- scientific article; zbMATH DE number 146671 (Why is no real title available?)
- Distance three labelings of trees
- The chromatic number of the square of the 8-cube
- Distance colorings of hypercubes from \(\mathbb{Z}_2 \mathbb{Z}_4\)-linear codes
- On \(b\)-coloring of powers of hypercubes
- Eigenvalue bounds for the distance-t chromatic number of a graph and their application to Lee codes
- On a hypercube coloring problem
- Abelian groups without 3-chromatic Cayley graphs
- The 2-distance coloring of the Cartesian product of cycles using optimal Lee codes
- BCH codes and distance multi- or fractional colorings in hypercubes asymptotically
- The \(L(h,1,1)\)-labelling problem for trees
This page was built for publication: New bounds on a hypercube coloring problem.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1853150)
