  We present polynomial-time SDP-based algorithms for the following problem:
For fixed $k \leq \ell$, given a real number $\epsilon>0$ and a graph $G$ that
admits a $k$-colouring with a $\rho$-fraction of the edges coloured properly,
it returns an $\ell$-colouring of $G$ with an $(\alpha \rho -
\epsilon)$-fraction of the edges coloured properly in polynomial time in $G$
and $1 / \epsilon$. Our algorithms are based on the algorithms of Frieze and
Jerrum [Algorithmica'97] and of Karger, Motwani and Sudan [JACM'98].
  For $k = 2, \ell = 3$, our algorithm achieves an approximation ratio $\alpha
= 1$, which is the best possible. When $k$ is fixed and $\ell$ grows large, our
algorithm achieves an approximation ratio of $\alpha = 1 - o(1 / \ell)$. When
$k, \ell$ are both large, our algorithm achieves an approximation ratio of
$\alpha = 1 - 1 / \ell + 2 \ln \ell / k \ell - o(\ln \ell / k \ell) - O(1 /
k^2)$; if we fix $d = \ell - k$ and allow $k, \ell$ to grow large, this is
$\alpha = 1 - 1 / \ell + 2 \ln \ell / k \ell - o(\ln \ell / k \ell)$.
  By extending the results of Khot, Kindler, Mossel and O'Donnell [SICOMP'07]
to the promise setting, we show that for large $k$ and $\ell$, assuming Khot's
Unique Games Conjecture (UGC), it is \NP-hard to achieve an approximation ratio
$\alpha$ greater than $1 - 1 / \ell + 2 \ln \ell / k \ell + o(\ln \ell / k
\ell)$, provided that $\ell$ is bounded by a function that is
$o(\exp(\sqrt[3]{k}))$. For the case where $d = \ell - k$ is fixed, this bound
matches the performance of our algorithm up to $o(\ln \ell / k \ell)$.
Furthermore, by extending the results of Guruswami and Sinop [ToC'13] to the
promise setting, we prove that it is NP-hard to achieve an approximation ratio
greater than $1 - 1 / \ell + 8 \ln \ell / k \ell + o(\ln \ell / k \ell)$,
provided again that $\ell$ is bounded as before (but this time without assuming
the UGC).
