Minimal separators in graph classes defined by small forbidden induced\n subgraphs

2019/03/11 by Martin Milanič, Milanič, Martin, Nevena Pivač +1
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Optimization and Search Problems

paper · pdf · doi:10.48550/arxiv.1903.04534

openalex publication_date 2019/03/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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

Related

• Characterization by forbidden induced subgraphs of some subclasses of chordal graphs
• A Characterization of all Stable Minimal Separator Graphs
• A tame vs. feral dichotomy for graph classes excluding an induced minor or induced topological minor
• Finding a Maximum Minimal Separator: Graph Classes and Fixed-Parameter Tractability
• On classes of graphs with strongly sublinear separators