文章基本信息

标题：Finding Large H-Colorable Subgraphs in Hereditary Graph Classes
本地全文：下载
作者：Maria Chudnovsky ; Jason King ; Micha{\l} Pilipczuk 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：173
页码：35:1-35:17
DOI：10.4230/LIPIcs.ESA.2020.35
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：homomorphisms; hereditary graph classes; odd cycle transversal