Covering minimal separators and potential maximal cliques in \(P_t\)-free graphs

DOI10.37236/9473zbMath1458.05194arXiv2003.12345OpenAlexW3129306252MaRDI QIDQ2227825

Tereza Klimošová, Michał Pilipczuk, Marcin Pilipczuk, Andrzej Grzesik

Publication date: 16 February 2021

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

maximum weight independent setseparator covering lemma

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• A survey of the algorithmic aspects of modular decomposition
• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
• On maximal independent sets of vertices in claw-free graphs
• Listing all potential maximal cliques of a graph
• 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
• Closing complexity gaps for coloring problems on \(H\)-free 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
• Treewidth and Minimum Fill-in: Grouping the Minimal Separators
• Large Induced Subgraphs via Triangulations and CMSO
• Independence and Efficient Domination on P ₆ -free Graphs
• 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

This page was built for publication: Covering minimal separators and potential maximal cliques in \(P_t\)-free graphs