2026-07-20T05:38:28Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12901 2024-03-06T10:51:02Z ddc:004 open_access

Finding Large H-Colorable Subgraphs in Hereditary Graph Classes Chudnovsky, Maria King, Jason Pilipczuk, Michał Rzążewski, Paweł Spirkl, Sophie homomorphisms hereditary graph classes odd cycle transversal 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₅,F}-free graphs in polynomial time, whenever F is a threshold graph; - in {P₅,bull}-free graphs in polynomial time; - in P₅-free graphs in time n^𝒪(ω(G)); - in {P₆,1-subdivided claw}-free graphs in time n^𝒪(ω(G)³). 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₅-free and for {P₆,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₅-free graphs, if we allow loops on H. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Maria Chudnovsky and Jason King and Michał Pilipczuk and Paweł Rzążewski and Sophie Spirkl 2020 Is Part Of LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2020.35 urn:nbn:de:0030-drops-129019 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.35 eng https://creativecommons.org/licenses/by/3.0/legalcode