New results on two hypercube coloring problems

DOI10.1016/J.DAM.2013.07.006MaRDI QIDQ2446885zbMATH OpenOpenAlexFDO

Authors San Ling, Fangwei Fu, Chaoping Xing

Publication date 23 April 2014

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1001.2209

zbMATH Keywords

\(\mathbb Z_4\)-linear codescoding theorycoloring problemforbidden distance codeshypercubelinear codes

Mathematics Subject Classification ID

Distance in graphs (05C12) Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65) Linear codes (general theory) (94B05)

Abstract: In this paper, we study the following two hypercube coloring problems: Given $n$ and $d$, find the minimum number of colors, denoted as $chi{\text{'}}_d(n)$ (resp. ${chi}_d(n)$), needed to color the vertices of the $n$-cube such that any two vertices with Hamming distance at most $d$ (resp. exactly $d$) have different colors. These problems originally arose in the study of the scalability of optical networks. Using methods in coding theory, we show that $chi{\text{'}}_4(2^{r+1}-1)=2^{2r+1}$, $chi{\text{'}}_5(2^{r+1})=4^{r+1}$ for any odd number $rgeq3$, and give two upper bounds on ${chi}_d(n)$. The first upper bound improves on that of Kim, Du and Pardalos. The second upper bound improves on the first one for small $n$. Furthermore, we derive an inequality on ${chi}_d(n)$ and $chi{\text{'}}_d(n)$.

Recommendations

• New bounds on a hypercube coloring problem.
• A coloring problem on the \(n\)-cube
• On a hypercube coloring problem
• On a coloring problem on the n-cube
• scientific article; zbMATH DE number 146671

Cites work

• A coloring problem on the \(n\)-cube
• A distance-labelling problem for hypercubes
• BCH codes and distance multi- or fractional colorings in hypercubes asymptotically
• Codes with forbidden distances
• Codes with given distances
• scientific article; zbMATH DE number 5139444 (Why is no real title available?)
• scientific article; zbMATH DE number 3577144 (Why is no real title available?)
• scientific article; zbMATH DE number 1284417 (Why is no real title available?)
• scientific article; zbMATH DE number 1142361 (Why is no real title available?)
• scientific article; zbMATH DE number 1775058 (Why is no real title available?)
• scientific article; zbMATH DE number 821271 (Why is no real title available?)
• Matroidal bijections between graphs
• Near-optimal conflict-free channel set assignments for an optical cluster-based hypercube network
• New bounds on a hypercube coloring problem.
• On a hypercube coloring problem
• On the acyclic chromatic number of Hamming graphs
• On the distance chromatic number of Hamming graphs
• Orthogonal vectors in the n-dimensional cube and codes with missing distances
• Some maximum multigraphs and adge/vertex distance colourings
• The Z/sub 4/-linearity of Kerdock, Preparata, Goethals, and related codes

Cited in

(17)

• On the acyclic chromatic number of Hamming graphs
• A coloring problem on the \(n\)-cube
• New bounds on a hypercube coloring problem.
• Multicolor routing in the undirected hypercube
• On robust colorings of Hamming-distance graphs
• The number of 4-colorings of the Hamming cube
• Exact distance graphs of product graphs
• Linear \(d\)-polychromatic \(Q_{d-1}\)-colorings of the hypercube
• Two coloring problems on matrix graphs
• Incidence coloring on hypercubes
• On a coloring problem on the n-cube
• scientific article; zbMATH DE number 146671 (Why is no real title available?)
• Distance colorings of hypercubes from \(\mathbb{Z}_2 \mathbb{Z}_4\)-linear codes
• Packing coloring of hypercubes with extended Hamming codes
• On a hypercube coloring problem
• Quantum chromatic number of subgraphs of orthogonality graphs and the distance-2 Hamming graph
• BCH codes and distance multi- or fractional colorings in hypercubes asymptotically

Describes a project that uses

Uses Software

• Code Tables

This page was built for publication: New results on two hypercube coloring problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2446885)