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

DOI10.37236/9428MaRDI QIDQ2656894zbMATH OpenOpenAlexFDO

Authors Martin Milanič, Nevena Pivač

Publication date 17 March 2021

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

Copyright license Creative Commons Attribution 4.0 International

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

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

hereditary graph classgraphs of bounded clique cover number

Mathematics Subject Classification ID

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

Recommendations

• Graphs with polynomially many minimal separators
• On the number of minimal separators in graphs
• On the number of minimal separators in graphs
• Minimal separators in \(P_4\)-tidy graphs
• Publication:4944975

Cites work

• scientific article; zbMATH DE number 861332 (Why is no real title available?)
• scientific article; zbMATH DE number 1420906 (Why is no real title available?)
• scientific article; zbMATH DE number 7378380 (Why is no real title available?)
• 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
• A survey on the computational complexity of coloring graphs with forbidden subgraphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• Algorithmic graph theory and perfect graphs
• Characterizations and algorithmic applications of chordal graph embeddings
• Claw-freeness, 3-homogeneous subsets of a graph and a reconstruction problem
• Clique-cutsets beyond chordal graphs
• Clique-width for 4-vertex forbidden subgraphs
• Clique-width for hereditary graph classes
• Computing the treewidth and the minimum fill-in with the modular decomposition
• Decomposition by clique separators
• Efficient subgraphs packing
• Finding induced subgraphs via minimal triangulations
• Large Induced Subgraphs via Triangulations and CMSO
• Linear separation of connected dominating sets in graphs
• Listing all potential maximal cliques of a graph
• Minimal separators in \(P_4\)-sparse graphs
• Minimal separators in extended \(P_4\)-laden graphs
• Minimal separators in graph classes defined by small forbidden induced subgraphs
• Minimal triangulations of graphs: a survey
• Minimum Fill-in on Circle and Circular-Arc Graphs
• On distance-\(d\) Independent Set and other problems in graphs with ``few minimal separators
• On graphs with polynomially solvable maximum-weight clique problem
• On rigid circuit graphs
• On the complexity of H-coloring
• On the vertex ranking problem for trapezoid, circular-arc and other graphs
• On treewidth and minimum fill-in of asteroidal triple-free graphs
• Oriented star packings
• Paw-free graphs
• STACS 2005
• Safe separators for treewidth
• Separability generalizes Dirac's theorem
• Separator orders in interval, cocomparability, and AT-free graphs
• TREEWIDTH OF CIRCLE GRAPHS
• The price of connectivity for cycle transversals
• To approximate treewidth, use treelength!
• Tournaments and colouring
• Towards an isomorphism dichotomy for hereditary graph classes
• Treewidth and Pathwidth of Permutation Graphs
• Treewidth and minimum fill-in: Grouping the minimal separators
• Treewidth computations. I: Upper bounds
• Treewidth. Computations and approximations

Cited in

(2)

• A lower bound on the number of elementary components of essentially disconnected generalized polyomino graphs
• Taming graphs with no large creatures and skinny ladders

Describes a project that uses

Uses Software

• ComputeTW

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2656894)