<p>Seemingly the earliest characterization of the graphs in which every minimal separator is an independent set appeared in T. A. McKee, "Independent separator graphs," <em>Utilitas Mathematica</em> <strong>73</strong> (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). </p>

CC BY-SA 3.0
2014-03-25T18:49:55.537Z
2014-03-25T18:49:55.537Z
Terry McKee
<p>There are two new papers on graphs without cycle having exactly one chord. Both mainly deal with coloring these graphs: 
<a href="http://arxiv.org/abs/1309.2749">http://arxiv.org/abs/1309.2749</a> and <a href="http://arxiv.org/abs/1311.1928">http://arxiv.org/abs/1311.1928</a>. </p>

<p>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).</p>

CC BY-SA 3.0
2013-11-22T18:57:45.620Z
2013-11-22T18:57:45.620Z
user13667
<p>Your graphs have been characterized by this paper <a href="http://arxiv.org/pdf/1103.2913.pdf">http://arxiv.org/pdf/1103.2913.pdf</a>. </p>

<p>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.</p>

<p>Graphs containing no cycle with exactly one chord have been studied in depth by 
Trotignon and Vuskovic, <em>A Structure Theorem for Graphs with No Cycle with a Unique Chord and Its Consequences</em>,  J. Graph Theory 63 (2010) 31-67 <a href="http://onlinelibrary.wiley.com/doi/10.1002/jgt.20405/abstract;jsessionid=43C5C8DC2BBC4E0A2092C3114D7FC454.d04t04">DOI</a>. 
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!)</p>

<p><strong>Edit</strong> (17 Sept 2013): Very recently (see <a href="http://www.worldscientific.com/doi/abs/10.1142/S1793830913500158?journalCode=dmaa&amp;">here</a>), 
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.</p>

CC BY-SA 3.0
2013-02-10T10:21:40.927Z
2013-09-17T16:23:57.823Z
2013-09-17T16:23:57.823Z
user13136
<p><strong>Background:</strong>
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.</p>

<p>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.</p>

<p><strong>My questions:</strong> 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. </p>

<reference-request><graph-theory><graph-algorithms>
Graphs in which every minimal separator is an independent set
user13667
# Graphs in which every minimal separator is an independent set

(Asked by: username_0 on 2013-02-10)

**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.

**Tags:** reference-request, graph-theory, graph-algorithms

---

## 3 answers

### Answer by username_2 on 2013-02-10. Score: 21 | Accepted answer

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](http://onlinelibrary.wiley.com/doi/10.1002/jgt.20405/abstract;jsessionid=43C5C8DC2BBC4E0A2092C3114D7FC454.d04t04).
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](http://www.worldscientific.com/doi/abs/10.1142/S1793830913500158?journalCode=dmaa&)),
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 by username_1 on 2014-03-25. Score: 11

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 by username_0 on 2013-11-22. Score: 5

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).


---

