Finding Large H-Colorable Subgraphs in Hereditary Graph Classes

DOI10.1137/20M1367660MaRDI QIDQ5163508zbMATH OpenOpenAlexFDO

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

Publication date 4 November 2021

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2004.09425

zbMATH Keywords

graph homomorphismmax partial \(H\)-coloring problemP5-free graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Abstract: We study the extsc{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 extsc{Odd Cycle Transversal}. We prove that for every fixed pattern graph $H$ without loops, extsc{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,extrmbull$-free graphs in polynomial time; $$ in $P_5$-free graphs in time $n^{mathcalO(omega(G))}$; $$ in $P_6,extrm1-subdividedclaw$-free graphs in time $n^{mathcalO(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, combining the mentioned algorithms for $P_5$-free and for $P_6,extrm1-subdividedclaw$-free graphs with a simple branching procedure, we obtain subexponential-time algorithms for extsc{Max Partial $H$-Coloring} in these classes of graphs. Finally, we show that even a restricted variant of extsc{Max Partial $H$-Coloring} is $mathsfNP$-hard in the considered subclasses of $P_5$-free graphs, if we allow loops on $H$.

Recommendations

• scientific article; zbMATH DE number 7651174
• Hereditary graph classes: When the complexities of <scp>coloring</scp> and <scp>clique cover</scp> coincide
• Parameterized complexity of finding subgraphs with hereditary properties on hereditary graph classes
• Complexity of C_K-coloring in hereditary classes of graphs
• Complexity of \(C_k\)-coloring in hereditary classes of graphs
• scientific article; zbMATH DE number 1286302
• scientific article; zbMATH DE number 1983292
• Locally bounded hereditary subclasses of k-colourable graphs
• Some new hereditary classes where graph coloring remains NP-hard
• On the complexity of the vertex 3-coloring problem for the hereditary graph classes with forbidden subgraphs of small size

Cites work

• \(H\)-colouring \(P_t\)-free graphs in subexponential time
• A dichotomy for minimum cost graph homomorphisms
• A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
• A subexponential-time algorithm for the maximum independent set problem in \(P_t\)-free graphs
• A survey of the algorithmic aspects of modular decomposition
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• Bi‐arc graphs and the complexity of list homomorphisms
• Bounding the Mim-Width of Hereditary Graph Classes.
• Chordal co-gem-free and (\(P_{5}\),\,gem)-free graphs have bounded clique-width
• Closing complexity gaps for coloring problems on \(H\)-free graphs
• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
• Finding large induced sparse subgraphs in c _>t -free graphs in quasipolynomial time
• Four-coloring \(P_6\)-free graphs
• scientific article; zbMATH DE number 1003286 (Why is no real title available?)
• scientific article; zbMATH DE number 2117181 (Why is no real title available?)
• scientific article; zbMATH DE number 1456953 (Why is no real title available?)
• Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
• Independent set in P₅-free graphs in polynomial time
• Large Induced Subgraphs via Triangulations and CMSO
• Linear time solvable optimization problems on graphs of bounded clique-width
• List k-colouring P_t-free graphs: a mim-width perspective
• Odd holes in bull-free graphs
• On cycle transversals and their connected variants in the absence of a small linear forest
• On maximal independent sets of vertices in claw-free graphs
• Parameterized algorithms
• Polynomial-time algorithm for maximum weight independent set on \(P_6\)-free graphs
• Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs
• Subexponential algorithms for variants of the homomorphism problem in string graphs
• Subexponential-time algorithms for finding large induced sparse subgraphs
• Subexponential-time algorithms for maximum independent set in \(P_t\)-free and broom-free graphs
• The Erdős-Hajnal conjecture for bull-free graphs
• The maximum k-colorable subgraph problem for chordal graphs
• Three-coloring and list three-coloring of graphs without induced paths on seven vertices

Cited in

(8)

• Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs
• Parameterized complexity of finding subgraphs with hereditary properties on hereditary graph classes
• On algorithmic applications of sim-width and mim-width of (H₁,H₂)-free graphs
• scientific article; zbMATH DE number 1286302 (Why is no real title available?)
• Some new hereditary classes where graph coloring remains NP-hard
• scientific article; zbMATH DE number 7651174 (Why is no real title available?)
• Odd cycle transversal on P₅-free graphs in polynomial time
• A polynomial bound on the number of minimal separators and potential maximal cliques in P₆-free graphs of bounded clique number

This page was built for publication: Finding Large $H$-Colorable Subgraphs in Hereditary Graph Classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5163508)