Polynomially bounding the number of minimal separators in graphs: reductions, sufficient conditions, and a dichotomy theorem

DOI10.37236/9428zbMath1459.05277OpenAlexW3137869160MaRDI QIDQ2656894

Nevena Pivač, Martin Milanič

Publication date: 17 March 2021

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

Full work available at URL: https://doi.org/10.37236/9428

zbMATH Keywords

hereditary graph classgraphs of bounded clique cover number

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Structural characterization of families of graphs (05C75) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Connectivity (05C40) Graph operations (line graphs, products, etc.) (05C76)

Uses Software

• ComputeTW

Cites Work

• A complexity dichotomy and a new boundary class for the dominating set problem
• A polynomial Turing-kernel for weighted independent set in bull-free graphs
• Separator orders in interval, cocomparability, and AT-free graphs
• The price of connectivity for cycle transversals
• On rigid circuit graphs
• Minimal triangulations of graphs: a survey
• Safe separators for treewidth
• Minimal separators in \(P_4\)-sparse graphs
• Treewidth computations. I: Upper bounds
• Decomposition by clique separators
• On the complexity of H-coloring
• Paw-free graphs
• Efficient subgraphs packing
• Treewidth. Computations and approximations
• Characterizations and algorithmic applications of chordal graph embeddings
• On treewidth and minimum fill-in of asteroidal triple-free graphs
• Separability generalizes Dirac's theorem
• Computing the treewidth and the minimum fill-in with the modular decomposition
• Listing all potential maximal cliques of a graph
• Towards an isomorphism dichotomy for hereditary graph classes
• Minimal separators in extended \(P_4\)-laden graphs
• Algorithmic graph theory and perfect graphs
• Tournaments and colouring
• On the vertex ranking problem for trapezoid, circular-arc and other graphs
• Minimal separators in graph classes defined by small forbidden induced subgraphs
• Clique-width for 4-vertex forbidden subgraphs
• Oriented star packings
• Treewidth and Minimum Fill-in: Grouping the Minimal Separators
• Large Induced Subgraphs via Triangulations and CMSO
• A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
• Finding Induced Subgraphs via Minimal Triangulations
• On Distance-d Independent Set and Other Problems in Graphs with “few” Minimal Separators
• On graphs with polynomially solvable maximum-weight clique problem
• Algorithmic Aspects of Vertex Elimination on Graphs
• Minimum Fill-in on Circle and Circular-Arc Graphs
• Treewidth and Pathwidth of Permutation Graphs
• TREEWIDTH OF CIRCLE GRAPHS
• Clique-width for hereditary graph classes
• Linear separation of connected dominating sets in graphs
• Clique‐cutsets beyond chordal graphs
• Claw-freeness, 3-homogeneous subsets of a graph and a reconstruction problem
• STACS 2005
• To Approximate Treewidth, Use Treelength!
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Polynomially bounding the number of minimal separators in graphs: reductions, sufficient conditions, and a dichotomy theorem