On Robust Colorings of Hamming-Distance Graphs

Authors

Isaiah Harney, University of KentuckyFollow
Heide Gluesing-Luerssen, University of KentuckyFollow

Abstract

H_q(n, d) is defined as the graph with vertex set Zⁿ_q 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 H₂(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 H₂ (n, n − 1) is presented.

Document Type

Article

Publication Date

10-5-2018

Notes/Citation Information

Published in The Electronic Journal of Combinatorics, v. 25, issue 4, paper #P4.3, p. 1-22.

© The authors.

Released under the CC BY-ND license (International 4.0).

Funding Information

HGL was partially supported by the National Science Foundation Grant DMS-1210061.

Repository Citation

Harney, Isaiah and Gluesing-Luerssen, Heide, "On Robust Colorings of Hamming-Distance Graphs" (2018). Mathematics Faculty Publications. 34.
https://uknowledge.uky.edu/math_facpub/34