A graph is called AT-free if it does not
contain a triple of mutually independent vertices such
that, between any two of them, there exists a path that
avoids the neighborhood of the third. A
triangulation of a graph is a chordal supergraph on
the same vertex set. In this paper, the class of
AT-free claw-free graphs (i.e., AT-free graphs
without an induced K1,3) is characterized as
exactly the class of graphs for that every
subseteq-minimal triangulation is a proper interval
graph. The proof relies on a new connection between the
subseteq-minimal triangulations of a graph and its
minimal separators. As a consequence, the treewidth,
the pathwidth and the bandwidth coincide for AT-free
claw-free graphs. Therefore, the {sc Bandwidth}
problem restricted to co-bipartite graphs is
NP}-hard. On the other hand, the k-{sc
Bandwidth} problem, which is W[t]-hard for all t in
the fixed parameter hierarchy, can be decided in linear
time for AT-free claw-free graphs, for any fixed k.
Finally, the subseteq-minimal triangulations of
Pk-free graphs, for kleq 5, are studied by
similar methods.
