## Abstract

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^{O(ω(G));} and in {P_{6}, 1-subdivided claw}-free graphs in time n^{O(ω(G)3)}. Here, n is the number of vertices of the input graph G and ω(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 NP-hard in the considered subclasses of P_{5}-free graphs if we allow loops on H.

Original language | English (US) |
---|---|

Pages (from-to) | 2357-2386 |

Number of pages | 30 |

Journal | SIAM Journal on Discrete Mathematics |

Volume | 35 |

Issue number | 4 |

DOIs | |

State | Published - 2021 |

## All Science Journal Classification (ASJC) codes

- General Mathematics

## Keywords

- Graph homomorphism
- Odd cycle transversal
- P-free graphs