  Consider a graph G = G(k,d,s) with vertex set the set of all k-letter words
over an alphabet of size d. An edge e = vw is in E iff v is distinct from w and
the last(first) k-s letters of v are identical to the first(last) k-s letters
of w. In this paper we show that G is Hamiltonian for all non-trivial values of
the parameters and obtain exact values for its chromatic number when s is
greater than or equal to k/2. We also obtain bounds when the chromatic number
is less than k/2.
