Minimal separators in graph classes defined by small forbidden induced subgraphs

DOI10.1007/978-3-030-30786-8_29arXiv1903.04534MaRDI QIDQ6315422FDOQ6315422

Publication date: 11 March 2019

Abstract: Minimal separators in graphs are an important concept in algorithmic graph theory. In particular, many problems that are NP-hard for general graphs are known to become polynomial-time solvable for classes of graphs with a polynomially bounded number of minimal separators. Several well-known graph classes have this property, including chordal graphs, permutation graphs, circular-arc graphs, and circle graphs. We perform a systematic study of the question which classes of graphs defined by small forbidden induced subgraphs have a polynomially bounded number of minimal separators. We focus on sets of forbidden induced subgraphs with at most four vertices and obtain an almost complete dichotomy, leaving open only two cases.

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Structural characterization of families of graphs (05C75)

This page was built for publication: Minimal separators in graph classes defined by small forbidden induced subgraphs

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