$H_q(n,d)$ is defined as the graph with vertex set $\mathbb{Z}_q^n$ 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_2(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_2(n,n-1)$ is presented.
@article{10_37236_6495,
author = {Isaiah Harney and Heide Gluesing-Luerssen},
title = {On robust colorings of {Hamming-distance} graphs},
journal = {The electronic journal of combinatorics},
year = {2018},
volume = {25},
number = {4},
doi = {10.37236/6495},
zbl = {1398.05088},
url = {http://geodesic.mathdoc.fr/articles/10.37236/6495/}
}
TY - JOUR
AU - Isaiah Harney
AU - Heide Gluesing-Luerssen
TI - On robust colorings of Hamming-distance graphs
JO - The electronic journal of combinatorics
PY - 2018
VL - 25
IS - 4
UR - http://geodesic.mathdoc.fr/articles/10.37236/6495/
DO - 10.37236/6495
ID - 10_37236_6495
ER -
%0 Journal Article
%A Isaiah Harney
%A Heide Gluesing-Luerssen
%T On robust colorings of Hamming-distance graphs
%J The electronic journal of combinatorics
%D 2018
%V 25
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/6495/
%R 10.37236/6495
%F 10_37236_6495
Isaiah Harney; Heide Gluesing-Luerssen. On robust colorings of Hamming-distance graphs. The electronic journal of combinatorics, Tome 25 (2018) no. 4. doi: 10.37236/6495
