首页|Graphs with polynomially many minimal separators
Graphs with polynomially many minimal separators
扫码查看
点击上方二维码区域，可以放大扫码查看
原文链接
NSTL
Elsevier
We show that graphs that do not contain a theta, pyramid, prism, or turtle as an induced subgraph have polynomially many minimal separators. This result is the best possible in the sense that there are graphs with exponentially many minimal separators if only three of the four induced subgraphs are excluded. As a consequence, there is a polynomial time algorithm to solve the maximum weight independent set problem for the class of (theta, pyramid, prism, turtle)-free graphs. Since every prism, theta, and turtle contains an even hole, this also implies a polynomial time algorithm to solve the maximum weight independent set problem for the class of (pyramid, even hole)-free graphs. (c) 2021 Elsevier Inc. All rights reserved.
NSTL
Elsevier
