  The theory of kernelization can be used to rigorously analyze data reduction
for graph coloring problems. Here, the aim is to reduce a q-Coloring input to
an equivalent but smaller input whose size is provably bounded in terms of
structural properties, such as the size of a minimum vertex cover. In this
paper we settle two open problems about data reduction for q-Coloring.
  First, we obtain a kernel of bitsize $O(k^{q-1}\log{k})$ for q-Coloring
parameterized by Vertex Cover, for any q >= 3. This size bound is optimal up to
$k^{o(1)}$ factors assuming NP is not a subset of coNP/poly, and improves on
the previous-best kernel of size $O(k^q)$. We generalize this result for
deciding q-colorability of a graph G, to deciding the existence of a
homomorphism from G to an arbitrary fixed graph H. Furthermore, we can replace
the parameter vertex cover by the less restrictive parameter twin-cover. We
prove that H-Coloring parameterized by Twin-Cover has a kernel of size
$O(k^{\Delta(H)}\log k)$.
  Our second result shows that 3-Coloring does not admit non-trivial
sparsification: assuming NP is not a subset of coNP/poly, the parameterization
by the number of vertices n admits no (generalized) kernel of size $O(n^{2-e})$
for any e > 0. Previously, such a lower bound was only known for coloring with
q >= 4 colors.
