On robust colorings of hamming-distance graphs

Research output: Contribution to journalArticlepeer-review

Abstract

Hq (n, d) is defined as the graph with vertex set ℤnq and where two vertices are adjacent if their Hamming distance is at least d. The chromatic number of these graphs is presented for various sets of parameters (q, n, d). For the 4-colorings of the graphs H2 (n, n−1) a notion of robustness is introduced. It is based on the tolerance of swapping colors along an edge without destroying properness of the coloring. An explicit description of the maximally robust 4-colorings of H2 (n, n − 1) is presented.

Original languageEnglish
Article number#P4.3
JournalElectronic Journal of Combinatorics
Volume25
Issue number4
DOIs
StatePublished - Oct 5 2018

Bibliographical note

Publisher Copyright:
© The authors.

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'On robust colorings of hamming-distance graphs'. Together they form a unique fingerprint.

Cite this