This thesis consists of two parts. In the second part the research papers that constitute the
new results of the thesis are presented. In this first part we want to put these results in a …

A graph class is said to be tame if graphs in the class have a polynomially bounded number
of minimal separators. Tame graph classes have good algorithmic properties, which follow …

In this paper we consider the recognition of some probe graph classes. Given a class of
graphs G, a graph G is a probe graph of G if its vertices can be partitioned into a set ℙ of …

A graph G=(V,E) is a chordal probe graph if its vertices can be partitioned into two sets, P
(probes) and N (non-probes), where N is a stable set and such that G can be extended to a …

A minimal separator in a graph is an inclusion-minimal set of vertices that separates some
fixed pair of nonadjacent vertices. A graph class is said to be tame if there exists a …

Cographs are those graphs without induced path on four vertices. A graph G is a probe
cograph if its vertex set can be partitioned into two sets, N (non-probes) and P (probes) …

Given a class of graphs \calG, a graph G is a probe graph of \calG if its vertices can be
partitioned into two sets ℙ (the probes) and ℕ (nonprobes), where ℕ is an independent set …

An undirected graph G=(V, E) is a probe split graph if its vertex set can be partitioned into
two sets, N (non-probes) and P (probes) where N is independent and there exists E'⊆ N× N …

Given a class of graphs G, a graph G is a probe graph of G if its vertices can be partitioned
into a set of probes and an independent set of nonprobes such that G can be embedded into …

The interval graph for a set of intervals on a line consists of one vertex for each interval, and
an edge for each intersecting pair of intervals. A probe interval graph is a variant that is …