This paper investigates the \(k\)-distant chromatic number \(\chi_{\overline k}(n)\) of the graph of the \(n\)-dimensional hypercube, which also may be considered as the smallest number of binary codes with minimum distance \(k+1\) forming a partition of the \(n\)-dimensional binary Hamming space. Some lemmas and preparatory theorems present inequalities for \(\chi_{\overline 2}(n)\) and \(\chi_{\overline 3}(n)\); their proofs partially also make use of nonbinary codes. As a main result the asymptotic behaviour of those numbers is given: \(\chi_{\overline 2}(n)\sim n\) and \(\chi_{\overline 3}(n)\sim 2n\) as \(n\) tends to infinity.
- 25 pretty graph colouring problems
- A coloring problem in Hamming spaces
- A coloring problem on the \(n\)-cube
- scientific article; zbMATH DE number 3577144 (Why is no real title available?)
- scientific article; zbMATH DE number 1775058 (Why is no real title available?)
- scientific article; zbMATH DE number 3392570 (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.
- The triply shortened binary Hamming code is optimal
- Unit sphere packings and coverings of the Hamming space
- 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
- Graph 2-rankings
- New bounds on a hypercube coloring problem.
- On robust colorings of Hamming-distance graphs
- The number of 4-colorings of the Hamming cube
- The clique distribution in powers of hypercubes
- On transitive uniform partitions of \(F^n\) into binary Hamming codes
- On coupon colorings of graphs
- On the complexity of restoring corrupted colorings
- New results on two hypercube coloring problems
- BCH codes are good for distance multicolorings with radio frequencies in hypercubes asymptotically
- 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
- Acyclic homomorphisms to stars of graph Cartesian products and chordal bipartite graphs
- The chromatic number of the square of the 8-cube
- scientific article; zbMATH DE number 7310103 (Why is no real title available?)
- Distance colorings of hypercubes from \(\mathbb{Z}_2 \mathbb{Z}_4\)-linear codes
- On the distance chromatic number of Hamming graphs
- On \(b\)-coloring of powers of hypercubes
- Packing coloring of hypercubes with extended Hamming codes
- Injective coloring of generalized Mycielskian of graphs
- Parameterized complexity of coupon coloring of 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
- On a heterochromatic number for hypercubes
This page was built for publication: On a hypercube coloring problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q703683)
