Graphs in which every minimal separator is an independent set

Question

Background: Let $u, v$ be two vertices of an undirected graph $G=(V,E)$. A vertex set $S\subseteq V$ is a $u,v$-separator if $u$ and $v$ belong to different connected components of $G-S$. If no proper subset of a $u,v$-separator $S$ is a $u,v$-separator then $S$ is a minimal $u,v$-separator. A vertex set $S\subseteq V$ is a (minimal) separator if there exist vertices $u, v$ such that $S$ is a (minimal) $u,v$-separator.

A well-known theorem of G. Dirac states that a graph has no induced cycles of length at least four (called triangulated or chordal graph) if and only if every of its minimal separators is a clique. It is also well-known that triangulated graphs can be recognized in polynomial time.

My questions: What are graphs in which every minimal separator is an independent set? Are these graphs studied? And what is the recognition complexity of these graphs? Examples for such graphs include trees and cycles.

Answer 1

Your graphs have been characterized by this paper http://arxiv.org/pdf/1103.2913.pdf.

Edit: In the paper above it is proved that graphs in which every minimal separator is an independent set are exactly those containing no cycle with exactly one chord.

Graphs containing no cycle with exactly one chord have been studied in depth by Trotignon and Vuskovic, A Structure Theorem for Graphs with No Cycle with a Unique Chord and Its Consequences, J. Graph Theory 63 (2010) 31-67 DOI. As a result of this paper, these graphs can be recognized in polynomial time. (However, this paper did not point out the connection to independent minimal separators!)

Edit (17 Sept 2013): Very recently (see here), Terry Mckee describes all graphs in which every minimal vertex separator is a clique or an independent set. It turns out that these are the ''edge sums'' of chordal graphs and graphs in which every minimal vertex separator is an independent set.

Answer 2

Seemingly the earliest characterization of the graphs in which every minimal separator is an independent set appeared in T. A. McKee, "Independent separator graphs," Utilitas Mathematica 73 (2007) 217--224. These are precisely the graphs in which no cycle has a unique chord (or, equivalently, in which, in every cycle, every chord has a crossing chord).

Answer 3

There are two new papers on graphs without cycle having exactly one chord. Both mainly deal with coloring these graphs: http://arxiv.org/abs/1309.2749 and http://arxiv.org/abs/1311.1928.

The later also gives an $O(m^2n)$ recognition algorithm. But a faster one in time $O(mn)$ is already provided in the paper by Trotignon and Vuskovic (cited in answer by user13136).