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.