Finding large H-colorable subgraphs in hereditary graph classes

Maria Chudnovsky, Jason King, Michał Pilipczuk, Paweł Rzążewski, Sophie Spirkl

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

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 {P5, F}-free graphs in polynomial time, whenever F is a threshold graph; in {P5, bull}-free graphs in polynomial time; in P5-free graphs in time nO(ω(G)); in {P6, 1-subdivided claw}-free graphs in time nO(ω(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 P5-free and for {P6, 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 P5-free graphs, if we allow loops on H.

Original languageEnglish (US)
Title of host publication28th Annual European Symposium on Algorithms, ESA 2020
EditorsFabrizio Grandoni, Grzegorz Herman, Peter Sanders
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771627
DOIs
StatePublished - Aug 1 2020
Event28th Annual European Symposium on Algorithms, ESA 2020 - Virtual, Pisa, Italy
Duration: Sep 7 2020Sep 9 2020

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume173
ISSN (Print)1868-8969

Conference

Conference28th Annual European Symposium on Algorithms, ESA 2020
Country/TerritoryItaly
CityVirtual, Pisa
Period9/7/209/9/20

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Hereditary graph classes
  • Homomorphisms
  • Odd cycle transversal

Fingerprint

Dive into the research topics of 'Finding large H-colorable subgraphs in hereditary graph classes'. Together they form a unique fingerprint.

Cite this