On the separability of graphs

Recently, Cicalese and Milanič introduced a graph-theoretic concept called separability. A graph is said to be kk-separable   if any two non-adjacent vertices can be separated by the removal of at most kk vertices. The separability   of a graph GG is the least kk for which GG is kk-separable. In this paper, we investigate this concept under the following three aspects.First, we characterize the graphs for which in any non-complete connected induced subgraph the connectivity equals the separability, so-called separability-perfect graphs. We list the minimal forbidden induced subgraphs of this condition and derive a complete description of the separability-perfect graphs.We then turn our attention to graphs for which the separability is given locally by the maximum intersection of the neighborhoods of any two non-adjacent vertices. We prove that all (house, hole)-free graphs fulfill this property — a class properly including the chordal graphs and the distance-hereditary graphs. We conclude that the separability can be computed in O(mΔ)O(mΔ) time for such graphs.In the last part we introduce the concept of edge-separability, in analogy to edge-connectivity, and prove that the class of kk-edge-separable graphs is closed under topological minors for any kk. We explicitly give the forbidden topological minors of the kk-edge-separable graphs for each 0≤k≤30≤k≤3.