TY - JOUR

T1 - Finding large H-Colorable subgraphs in hereditary graph classes

AU - Chudnovsky, Maria

AU - King, Jason

AU - Pilipczuk, Michał

AU - Rzążewski, Paweł

AU - Spirkl, Sophie

N1 - Funding Information:
∗Received by the editors September 17, 2020; accepted for publication (in revised form) July 11, 2021; published electronically October 14, 2021. The extended abstract of this paper was presented on the conference ESA 2020, Pisa, Italy, 2020, pp. 35:1–35:17. https://doi.org/10.1137/20M1367660 Funding: The first author’s material is based upon work supported in part by the U.S. Army Research Office under grant W911NF-16-1-0404 and by NSF grant DMS-1763817. The third author’s work is a part of project TOTAL that has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant 677651). The fourth author was supported by Polish National Science Centre grant 2018/31/D/ST6/00062. The fifth author’s material is based upon work supported by the National Science Foundation under award DMS-1802201.
Publisher Copyright:
© 2021 Society for Industrial and Applied Mathematics

PY - 2021

Y1 - 2021

N2 - 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)); and 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.

AB - 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)); and 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.

KW - Graph homomorphism

KW - Odd cycle transversal

KW - P-free graphs

UR - http://www.scopus.com/inward/record.url?scp=85117162734&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85117162734&partnerID=8YFLogxK

U2 - 10.1137/20M1367660

DO - 10.1137/20M1367660

M3 - Article

AN - SCOPUS:85117162734

VL - 35

SP - 2357

EP - 2386

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

SN - 0895-4801

IS - 4

ER -