DOI: 10.1002/jgt.23098 ISSN: 0364-9024

# Bisimplicial separators

Martin Milanič, Irena Penev, Nevena Pivač, Kristina Vušković- Geometry and Topology
- Discrete Mathematics and Combinatorics

## Abstract

A *minimal separator* of a graph is a set such that there exist vertices with the property that separates from in , but no proper subset of does. For an integer , we say that a minimal separator is ‐*simplicial* if it can be covered by cliques and denote by the class of all graphs in which each minimal separator is ‐simplicial. We show that for each , the class is closed under induced minors, and we use this to show that the

Maximum Weight Stable Set

problem can be solved in polynomial time for . We also give a complete list of minimal forbidden induced minors for . Next, we show that, for , every nonnull graph in has a ‐simplicial vertex, that is, a vertex whose neighborhood is a union of cliques; we deduce that the
Maximum Weight Clique

problem can be solved in polynomial time for graphs in . Further, we show that, for , it is NP‐hard to recognize graphs in ; the time complexity of recognizing graphs in is unknown. We also show that the
Maximum Clique

problem is NP‐hard for graphs in . Finally, we prove a decomposition theorem for diamond‐free graphs in (where the *diamond*is the graph obtained from by deleting one edge), and we use this theorem to obtain polynomial‐time algorithms for the

Vertex Coloring

and recognition problems for diamond‐free graphs in , and improved running times for the
Maximum Weight Clique

and
Maximum Weight Stable Set

problems for this class of graphs.