Abstract:
Acyclic Clique-Interval Graphs
The class of acyclic clique-interval (ACI) graphs is
introduced as the class of those graphs $G$=($V$,$E$) whose
cliques are intervals (chains) of an acyclic order on the
vertex set $V$. The class of ACI graphs is related to the
classes of proper interval graphs, tree-clique graphs and to
the class DV (intersection graphs of directed paths of a
directed tree). Compatibility between a graph and an acyclic
order is defined, ACI graphs are characterized in terms of
it and some special sets of vertices are found by means of
the acyclic compatible order. ACI graphs are also
characterized in terms of the dual hypergraph of the
hypergraph of all cliques of $G$. Results concerning
substitution and reduction preserving the ACI status are
established. A strong necessary condition for a graph to be
an ACI graph is also given.