  We study the \textsc{Max Partial $H$-Coloring} problem: given a graph $G$,
find the largest induced subgraph of $G$ that admits a homomorphism into $H$,
where $H$ is a fixed pattern graph without loops. Note that when $H$ is a
complete graph on $k$ vertices, the problem reduces to finding the largest
induced $k$-colorable subgraph, which for $k=2$ is equivalent (by
complementation) to \textsc{Odd Cycle Transversal}.
  We prove that for every fixed pattern graph $H$ without loops, \textsc{Max
Partial $H$-Coloring} can be solved:
  $\bullet$ in $\{P_5,F\}$-free graphs in polynomial time, whenever $F$ is a
threshold graph;
  $\bullet$ in $\{P_5,\textrm{bull}\}$-free graphs in polynomial time;
  $\bullet$ in $P_5$-free graphs in time $n^{\mathcal{O}(\omega(G))}$;
  $\bullet$ in $\{P_6,\textrm{1-subdivided claw}\}$-free graphs in time
$n^{\mathcal{O}(\omega(G)^3)}$.
  Here, $n$ is the number of vertices of the input graph $G$ and $\omega(G)$ is
the maximum size of a clique in~$G$. Furthermore, combining the mentioned
algorithms for $P_5$-free and for $\{P_6,\textrm{1-subdivided claw}\}$-free
graphs with a simple branching procedure, we obtain subexponential-time
algorithms for \textsc{Max Partial $H$-Coloring} in these classes of graphs.
Finally, we show that even a restricted variant of \textsc{Max Partial
$H$-Coloring} is $\mathsf{NP}$-hard in the considered subclasses of $P_5$-free
graphs, if we allow loops on $H$.
