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 - 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
SN - 0895-4801
VL - 35
SP - 2357
EP - 2386
JO - SIAM Journal on Discrete Mathematics
JF - SIAM Journal on Discrete Mathematics
IS - 4
ER -