  Haramaty and Sudan considered the problem of transmitting a message between
two people, Alice and Bob, when Alice's and Bob's priors on the message are
allowed to differ by at most a given factor. To find a deterministic
compression scheme for this problem, they showed that it is sufficient to
obtain an upper bound on the chromatic number of a graph, denoted $U(N,s,k)$
for parameters $N,s,k$, whose vertices are nested sequences of subsets and
whose edges are between vertices that have similar sequences of sets. In turn,
there is a close relationship between the problem of determining the chromatic
number of $U(N,s,k)$ and a local graph coloring problem considered by Erd\H{o}s
et al. We generalize the results of Erd\H{o}s et al. by finding bounds on the
chromatic numbers of graphs $H$ and $G$ when there is a homomorphism $\phi
:H\rightarrow G$ that satisfies a nice property. We then use these results to
improve upper and lower bounds on $\chi(U(N,s,k))$.
