Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

3 Answers 3

up vote 21 down vote accepted

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.

share|improve this answer
    
Thank you for a lot of very useful facts! –  user13667 Feb 11 '13 at 9:10
add comment

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

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.