Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 1 of 1
Full-Text Articles in Mathematics
On Robust Colorings Of Hamming-Distance Graphs, Isaiah Harney, Heide Gluesing-Luerssen
On Robust Colorings Of Hamming-Distance Graphs, Isaiah Harney, Heide Gluesing-Luerssen
Mathematics Faculty Publications
Hq(n, d) is defined as the graph with vertex set Znq 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 …