Finding Large $H$-Colorable Subgraphs in Hereditary Graph Classes

DOI10.1137/20M1367660zbMath1478.05048arXiv2004.09425OpenAlexW3205762307MaRDI QIDQ5163508

Paweł Rzążewski, Maria Chudnovsky, Jason King, Michał Pilipczuk, 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

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

Related Items (1)

On algorithmic applications of sim-width and mim-width of \((H_1,H_2)\)-free graphs

Cites Work

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

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