Graphs with polynomially many minimal separators

DOI10.1016/j.jctb.2021.10.003zbMath1478.05084arXiv2005.05042OpenAlexW3209095404MaRDI QIDQ2664556

Nicolas Trotignon, Tara Abrishami, Maria Chudnovsky, Kristina Vušković, Cemil Dibek, Steéphan Thomassé

Publication date: 17 November 2021

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

prismpyramidinduced subgraphthetaminimal separatorturtle

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Cites Work

• Unnamed Item
• Stable sets and graphs with no even holes
• Listing all potential maximal cliques of a graph
• An introduction to clique minimal separator decomposition
• Treewidth and Minimum Fill-in: Grouping the Minimal Separators
• Finding Induced Subgraphs via Minimal Triangulations
• On rank-width of even-hole-free graphs
• Polynomial-time algorithm for Maximum Weight Independent Set on P₆-free graphs
• Independent Set in P₅-Free Graphs in Polynomial Time

This page was built for publication: Graphs with polynomially many minimal separators