Name
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 {P-5, F}-free graphs in polynomial time, whenever F is a threshold graph; in {P-5, bull}-free graphs in polynomial time; in P-5-free graphs in time n(O(omega(G))); and in {P-6, 1-subdivided claw}-free graphs in time n(O(omega(G)3)). Here, n is the number of vertices of the input graph G and omega(G) is the maximum size of a clique in G. Furthermore, by combining the mentioned algorithms for P-5-free and for {P-6, 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-5-free graphs if we allow loops on H. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1137/20M1367660 | SIAM JOURNAL ON DISCRETE MATHEMATICS |
Keywords | DocType | Volume |
odd cycle transversal, graph homomorphism, P-5-free graphs | Journal | 35 |
Issue | ISSN | Citations |
4 | 0895-4801 | 0 |
PageRank | References | Authors |
0.34 | 0 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Maria Chudnovsky | 1 | 390 | 46.13 |
| Jason King | 2 | 0 | 0.68 |
| michal pilipczuk | 3 | 403 | 51.93 |
| Pawel Rzazewski | 4 | 42 | 19.73 |
| Sophie Theresa Spirkl | 5 | 8 | 7.36 |