scientific article; zbMATH DE number 7651174

DOI10.4230/LIPIcs.ESA.2020.35MaRDI QIDQ5874504

Michał Pilipczuk, Maria Chudnovsky, Sophie Spirkl, Jason King, Paweł Rząėwski

Publication date: 7 February 2023

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

homomorphismshereditary graph classesodd cycle transversal

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Related Items (3)

Bounding the mim‐width of hereditary graph classes ⋮ List \(k\)-colouring \(P_t\)-free graphs: a mim-width perspective ⋮ Bounding the Mim-Width of Hereditary Graph Classes.

Cites Work

• 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
• 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
• 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
• 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
• Polynomial algorithm for finding the largest independent sets in graphs without forks
• 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
• A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
• Approximately coloring graphs without long induced paths
• Unnamed Item

This page was built for publication: