
arXiv: 1903.04534
handle: 20.500.12556/RUP-11979
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.
info:eu-repo/classification/udc/519.17:004, hereditary graph class, hereditaren razred grafov, forbidden induced subgraph, minimalen separator, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), minimal separator, prepovedan induciran podgraf
info:eu-repo/classification/udc/519.17:004, hereditary graph class, hereditaren razred grafov, forbidden induced subgraph, minimalen separator, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), minimal separator, prepovedan induciran podgraf
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 3 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
