Finding Large $H$-Colorable Subgraphs in Hereditary Graph Classes
Maria Chudnovsky, Jason King, Michał Pilipczuk, Paweł Rzążewski, Sophie Spirkl · SIAM Journal on Discrete Mathematics · 2021
We study the 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 Odd Cycle Transversal. We prove that for every fixed pattern graph $H$ without loops, Max Partial $H$-Coloring can be solved in $\{P_5,F\}$-free graphs in polynomial time, whenever $F$ is a threshold graph; in $\{P_5,{bull}\}$-free graphs in polynomial time; in $P_5$-free graphs in time $n^{\mathcal{O}(\omega(G))}$; and in $\{P_6,{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, by combining the mentioned algorithms for $P_5$-free and for $\{P_6,{1-subdivided claw}\}$-free graphs with a simple branching procedure, we obtain subexponential-time algorithms for Max Partial $H$-Coloring in these classes of graphs. Finally, we show that even a restricted variant of Max Partial $H$-Coloring is $\mathsf{NP}$-hard in the considered subclasses of $P_5$-free graphs if we allow loops on $H$.