% FINAL version for Electronic Journal of Combinatorics 2013
% EJC papers *must* begin with the following two lines. 
\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P5}{20(3)}{2013}

\sloppy
% Please remove all other commands that change parameters such as
% margins or pagesizes.

% only use standard LaTeX packages
% only include packages that you actually need

% we recommend these ams packages
\usepackage{amsthm,amsmath,amssymb}

% we recommend the graphicx package for importing figures
\usepackage{graphicx}

% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

% all overfull boxes must be fixed; 
% i.e. there must be no text protruding into the margins


% declare theorem-like environments

\theoremstyle{plain}
\begin{document}
\newcommand{\dom}{\mbox{$\rightarrow$}}
%\newtheorem{tm}{\hspace{6mm}Theorem}[section]
\newtheorem{tm}{\hspace{6mm}Theorem}
\newtheorem{prp}[tm]{\hspace{6mm}Proposition}
\newtheorem{dfn}[tm]{\hspace{6mm}Definition}
\newtheorem{lemma}[tm]{\hspace{6mm}Lemma}
\newtheorem{cor}[tm]{\hspace{6mm}Corollary}
\newtheorem{conj}[tm]{\hspace{6mm}Conjecture}
\newtheorem{quest}[tm]{\hspace{6mm}Question}
\newtheorem{alg}[tm]{\hspace{6mm}Algorithm}
\newtheorem{sub}[tm]{\hspace{6mm}Algorithm}
\newcommand{\ndom}{\mbox{$\not\rightarrow$}}
\newcommand{\lr}{\mbox{$\longrightarrow$}}

\newcommand{\pf}{\vspace{-3mm}\hspace{1mm}{\bf Proof: }}
\newcommand{\nl}{\hfill\break}
\newcommand{\emset}{\emptyset}
\newcommand{\lefa}{\leftarrow}

\title{\bf Recognition and Characterization of Chronological Interval Digraphs}

\author{Sandip Das\thanks{Advanced Computing and Microelectronics Unit,\
        Indian Statistical Institute,\
        Calcutta, India-700 035;\
        sandipdas@isical.ac.in}\quad\ \
        Mathew Francis\thanks{Department of Mathematics and Statistics,\
        University of Victoria,\
        P.O. Box 3060,\
        Victoria,\ B.C.,\ Canada,\ V8W\ 3R4;
	  mathewcfrancis@gmail.com}\quad\ \ 
        Pavol Hell\thanks{School of Computing Science,\
        Simon Fraser University,\
        Burnaby,\ B.C.,\
        Canada,\ V5A\ 1S6;\
        pavol@cs.sfu.ca}\quad\ \
     Jing Huang\thanks{Department of Mathematics and Statistics,\
        University of Victoria,\
        P.O. Box 3060,\
        Victoria,\ B.C.,\ Canada,\ V8W\ 3R4;
        jing@math.uvic.ca}}

\date{\dateline{July 2, 2012}{July 15, 2013}{July 26, 2013}}


\maketitle

\begin{abstract}
Interval graphs admit elegant ordering and structural characterizations 
as well as linear time recognition algorithms. On the other hand, the usual 
interval digraphs lack all three of these characteristics. In this paper we 
identify another natural digraph analogue of interval graphs that we call 
``chronological interval digraphs". By contrast, the new class admits an
ordering characterization, several forbidden substructure characterizations,
as well as a linear time recognition algorithm. Chronological interval digraphs 
arise by interpreting the standard definition of an interval graph with a 
natural orientation of its edges: $G$ is a chronological interval digraph 
if there exists a family of closed intervals $I_v, v \in V(G)$, such that $uv$ 
is an arc of $G$ if and only if $I_u$ contains the left endpoint of $I_v$.

We characterize chronological interval digraphs in terms of vertex orderings,
and in terms of two kinds of forbidden substructures. These characterizations 
exhibit strong similarity with the corresponding characterizations of interval 
graphs, and lead to a linear time recognition algorithm.
\end{abstract}


\section{Background}

All graphs and digraphs considered in this paper may contain loops but no multiple 
edges or arcs; they are called {\em reflexive} if there is a loop at every vertex. 
The vertex set of a graph or digraph $G$ is always denoted by $V(G)$.
If $G$ is a graph, we denote by $E(G)$ its edge set. If $G$ is a digraph, we denote
by $A(G)$ its arc set, and by $S(G)$ the set of all symmetric arcs 
(i.e., arcs $uv$ such that $vu$ is also an arc) in $A(G)$. Note that $S(G)$ 
contains all loops as each loop is symmetric. 

A graph $G$ is an {\em interval graph} if there exists a family of closed intervals 
$I_v, v \in V(G)$, called an {\em interval representation} of $G$, such that $uv$ 
is an edge of $G$ if and only if $I_u \cap I_v \neq \emptyset$. Interval graphs 
have been extensively studied, cf. e.g. \cite{golumbic}. The beautiful theory 
surrounding their study includes natural applications, elegant characterizations 
in terms of orderings and forbidden substructures, e.g., \cite{FG,GH,LB}, 
as well as linear time recognition algorithms, e.g. \cite{bl,derek}.

A digraph analogue of interval graphs, called interval digraphs, was pioneered 
in \cite{sdrw}. A digraph $G$ is an {\em interval digraph} if there exists a family 
of ordered pairs of closed intervals $(I_v, J_v), v \in V(G)$, also called an {\em
interval representation} of $G$, such that $uv$ is an arc in $G$ if and only if 
$I_u \cap J_v \neq \emptyset$. Interval digraphs have also been much studied
\cite{bbl,malay,ds,adjusted,h,muller,ssw,sdrw,west}. In particular, there are 
characterizations of interval digraphs in terms of matrices, as well as a 
polynomial time recognition algorithm. However, the most attractive aspects
of interval graphs are absent, namely, an ordering characterization, a forbidden 
substructure characterization, and a linear time time recognition algorithm. 
(The only known polynomial recognition algorithm \cite{muller} has complexity 
$O(nm^6(n+m)\log n)$.)

In this paper we propose a natural alternative digraph analogue of interval 
graphs. A digraph $G$ is a {\em chronological interval digraph} if there
exists a family of closed intervals $I_v, v \in V(G)$, called a {\em 
chronological interval representation} of $G$, such that $uv$ is an 
arc of $G$ if and only if $I_u$ contains the left endpoint of $I_v$.
(Equivalently, $uv$ is an arc of $G$ if and only if $I_u$ intersects $I_v$ 
and the left endpoint of $I_u$ is not greater than the left endpoint of $I_v$.)
Since every interval contains its own left endpoint, the digraph $G$ is reflexive. 
For the same reason, every interval graph is reflexive. In fact, 
an undirected graph is an interval graph if and only if it admits an 
orientation which is a chronological interval digraph. In this sense, our results 
provide new characterizations of interval graphs in terms of their orientations,
see Corollary \ref{pes}.

The possible orderings of endpoints of intervals representing an interval graph 
have been investigated under the name ``chronological orderings" \cite{skrien}. 
(In fact, ``chronological orderings" of interval bigraphs and digraphs have also 
been investigated in \cite{std}.) We adopt the adjective ``chronological" for our
digraphs.

Let $G$ be an interval digraph with an interval representation $(I_v, J_v), 
v \in V(G)$. If each interval $J_v$ is a single point, then $G$ is called 
an {\em interval catch digraph} \cite{prisner}. If each pair $I_v, J_v$ have 
the same left endpoint then $G$ is called an {\em adjusted interval digraph}, 
cf. \cite{adjusted,adjustedGROW}. If each $J_v$ is the single point
that is the left endpoint of $I_v$ then $I_v, v \in V(G),$ is a chronological
interval representation of $G$. Consequently, every chronological interval 
digraph is an interval catch digraph as well as an adjusted interval digraph. 
However, the converse is not true: for instance the digraph $Z$ in Figure~\ref{z}
has one representation with each interval $J_v$ being a single point, and another 
representation with each pair $I_v, J_v$ having the same left endpoint; however,
no representation satisfies both properties simultaneously.

We shall give three characterizations of chronological interval digraphs - an 
ordering characterization, a structural characterization similar to the theorem 
of Lekkerkerker and Boland \cite{LB}, and a novel characterization in terms 
of so-called parallel vertices. The last characterization leads to a linear time 
recognition algorithm for the class. We note that in the special case of acyclic 
digraphs, a different forbidden subgraph characterization of chronological 
interval digraphs has been described (without proof) in \cite{mm}.


\section{Preliminary structures}
\label{prelim}

We assume from now on that all digraphs $G$ are reflexive. When $uv \in A(G)$, 
we say that $v$ is an {\em out-neighbour} of $u$ and that $u$ is 
an {\em in-neighbour} of $v$. Note that each vertex $v$ is an out-neighbour 
as well as an in-neighbour of itself.
We use the symbol $N^+(v)$, respectively $N^-(v)$, to denote the set of 
out-neighbours, respectively in-neighbours, of a vertex $v$. 
The sizes $|N^+(v)|$ and $|N^-(v)|$ are respectively the {\em outdegree} and 
{\em indegree} of $v$.

A digraph is {\em complete} if any two vertices are joined by symmetric arcs
and is {\em semicomplete} if any two vertices are joined by at least one arc 
(which may or may not be symmetric). A digraph is {\em in-semicomplete} 
\cite{bhp} if the in-neighbours of each vertex induce a semicomplete subdigraph. 
A digraph $G$ is {\em clustered} if it is in-semicomplete and for any two 
vertices $u, v$ in the same strong component of $G$, we have $N^-(u) = N^-(v)$,
and $N^+(u) \subseteq N^+(v)$ or $N^+(v) \subseteq N^+(u)$.
Note that the condition $N^-(u) = N^-(v)$ implies that $uv \in S(G)$, that is,
every strong component of a clustered digraph is complete.

\begin{prp} \label{kona}
Every chronological interval digraph is clustered.
\end{prp} 

\pf 
Let $G$ be a chronological interval digraph and $I_v, v \in V(G)$ be 
a chronological interval representation of $G$. 
If $u, u'$ are both in-neighbours of a vertex $v$ in $G$, then $I_u, I_{u'}$ 
must intersect as they both contain the left endpoint of $I_v$, so there is 
at least one arc between $u, u'$. Hence $G$ is in-semicomplete.

Suppose that $u, v$ are in the same strong component of $G$. Then there exist
a directed path from $u$ to $v$ and a directed path from $v$ to $u$. 
It follows from the definition that the left endpoint of $I_u$ is not greater 
than the left endpoint of $I_v$ and vice versa. Consequently, 
the left endpoints of $I_u$ and $I_v$ are the same which means that $uv$ is 
a symmetric arc in $G$. Hence every strong component of $G$ is complete.  

Since $I_u$ and $I_v$ have the same left endpoint, $N^-(u) = N^-(v)$. 
Furthermore, $N^+(u) \subseteq N^+(v)$ if the right endpoint of $I_u$ is 
not greater than the right endpoint of $I_v$ and $N^+(v) \subseteq N^+(u)$ 
otherwise. Therefore $G$ is clustered.
\qed

The reflexive digraph $Z$ in Figure \ref{z} is not clustered as 
$N^+(a) \not\subseteq N^+(b)$ and $N^+(b) \not\subseteq N^+(a)$. Hence 
it cannot be an induced subdigraph of a chronological interval digraph.

\begin{figure}[hbtf]
\centerline{\includegraphics[height=24mm,width=19mm]{z.eps}}
\caption{The reflexive digraph $Z$ where the loops are not drawn}
\label{z}
\end{figure}

\begin{cor} \label{zz}
No chronological interval digraph contains $Z$ as an induced subdigraph.
\qed
\end{cor}

A digraph is {\em connected} if its underlying undirected graph is connected.
Clearly, a digraph is a chronological interval digraph if and only if this is 
so for each of its connected components. Therefore, we assume from now on that 
all digraphs considered are connected; this will not be repeated.

The following ordering characterization of interval graphs is well known.
An undirected graph $G$ is an interval graph if and only if $V(G)$ can
be linearly ordered by $<$ so that for $u, v, w \in V(G)$ with $u < v < w$
we have that $uw \in E(G)$ implies $ uv \in E(G)$, cf. \cite{skrien}.
Similarly, a digraph is an interval catch digraph if and only if $V(G)$ can
be linearly ordered by $<$ so that for $u, v, w \in V(G)$ with $u < v < w$
we have that $uw \in A(G)$ implies $ uv \in A(G)$, and $wu \in A(G)$ 
implies $ wv \in A(G)$ cf. \cite{prisner}. A digraph is an adjusted interval 
digraph if and only if $V(G)$ can be linearly ordered by $<$ so that for 
$u, v, w \in V(G)$ with $u < v < w$ we have that $uw \in A(G)$ implies 
$ uv \in A(G)$, and $wu \in A(G)$ implies $ vu \in A(G)$ cf. \cite{adjusted}.

There is an ordering characterization also for chronological interval digraphs. 
We say that a linear ordering $<$ of the vertices of a digraph $G$ is a {\em 
chronological ordering} of $G$ if it satisfies the following four properties, for
any $u < v$ (for $P_1$) and any $u < v < w$ (for $P_2 - P_4$).

\begin{enumerate}
\item[($P_1$)] $vu \not\in A(G) - S(G)$
\item[($P_2$)] $uw \in S(G)$ implies $uv, vw \in S(G)$
\item[($P_3$)] $uw \in A(G) - S(G)$ implies 
      either $uv \in A(G) - S(G)$ or both $uv \in S(G)$ and $vw \in A(G)-S(G)$
\item[($P_4$)] $uw \notin A(G)$ implies $uv \not\in A(G)$ or $vw \not\in S(G)$.
\end{enumerate}

The ordering can be intuitively described as follows. Each vertex $v$ forms
a maximal complete digraph $C(v)$ with some (possibly none) of its immediately 
preceding and some (possibly none) of its immediately following vertices. These
maximal complete digraphs comprise the strong components of $G$. If a vertex 
$u$ in $C(v)$ has an arc to a vertex in a $C(w)$, with $v < w$, then $u$ has an 
arc to each vertex of $C(w)$. 

\begin{prp} \label{ordering}
A digraph $G$ is a chronological interval digraph if and only if
it admits a chronological ordering.
\end{prp}

\pf Suppose $G$ is a chronological interval digraph.  Let 
$I_v = [l_v,r_v], v \in V(G)$ be a chronological interval representation of 
$G$. Assume without loss of generality that no two intervals are the same. 
Then the vertices of $G$ can be ordered lexicographically according to 
the ordered pairs of endpoints, that is, $u < v$ if and only if either 
$l_u < l_v$ or $l_u = l_v$ and $r_u < r_v$.
It is a routine exercise to check that this ordering $<$ 
is chronological. (Note that $uv \in S(G)$ if and only if $I_u$ and $I_v$
share the same left endpoint.)

Conversely, suppose that $v_1 < v_2 < \cdots < v_n$ is a 
chronological ordering of $G$. Then, for each $i = 1, 2, \dots, n$, 
there exist subscripts $a_i \leq  i \leq b_i \leq c_i$ such that 
$N^-(v_i) \cap N^+(v_i) = \{v_{a_i}, v_{a_i+1}, \dots, v_{b_i}\}$ and 
$N^+(v_i) = \{v_{a_i}, v_{a_i+1}, \dots, v_{c_i}\}$. It is easy to verify that
the intervals $I_{v_i} = [a_i, c_i]$, $i = 1, 2, \dots, n$, form 
a chronological interval representation of $G$. 
\qed

We pursue the analogy with interval graphs further as follows. A natural
obstruction to being an interval graph is the concept of an asteroidal
triple. Specifically, an {\em asteroidal triple} in a graph $G$ is a triple 
of vertices $a, b, c$, such that any two of them are joined by a path
that does not contain any neighbours of the third vertex. It is natural to
view an asteroidal triple as an obstruction to having an ordering $<$ 
such that, for $u < v < w$, the edge $uw \in E(G)$ implies the edge 
$ uv \in E(G)$. To make this explicit, we state the following equivalent 
definition of an asteroidal triple. An {\em asteroidal triple} in a graph $G$ 
is a triple of vertices $a, b, c$, such that for every ordering $u < v < w$ 
of $a, b, c$, there exists a sequence $u = u_1, u_2, \dots, u_p = w$ of 
vertices of $G$, such that for every $i = 1, 2, \dots, p-1$ the triple 
$u_i, v, u_{i+1}$ is ``bad'', in the sense that 
$$u_iu_{i+1} \in E(G)\ but\ u_iv \notin E(G)\ and\ vu_{i+1} \notin E(G).$$
Thus an asteroidal triple makes it impossible to find a suitable ordering
$<$. (It is worth noting that in this case the sequence $u = u_1, u_2, \dots, 
u_p = w$ is a path, a property we will lose in our analogue, due to the
difference in the definition of being ``bad".)

In a similar spirit we introduce a concept analogous to asteroidal triples.
An {\em asynchronous triple} in a digraph $G$ is a triple of vertices 
$a, b, c$, such that for every ordering $u < v < w$ of $a, b, c$, there exists 
a sequence $u = u_1, u_2, \dots, u_p = w$ of vertices of $G$, such that 
for every $i = 1, 2, \dots, p-1$ the triple $u_i, v, u_{i+1}$ is {\em bad}, 
in the sense that it violates one of the properties $P_1 - P_4$ above
(with $u, w$ replaced by $u_i, u_{i+1}$  respectively), that is, at least
one of the following four properties holds.

\begin{enumerate}
\item[($Q_1$)]
one of $vu_i, u_{i+1}v, u_{i+1}u_i$ is in $A(G) - S(G)$
\item[($Q_2$)]
$u_iu_{i+1} \in S(G)$ and at least one of 
         $u_iv \notin S(G), vu_{i+1} \notin S(G)$
\item[($Q_3$)]
$u_iu_{i+1} \in A(G) - S(G)$ and either $u_iv \notin A(G)$ or both
        $u_iv \in S(G)$ and $vu_{i+1} \notin A(G)-S(G)$
\item[($Q_4$)]
$u_iu_{i+1} \notin A(G)$, $u_iv \in A(G)$ and $vu_{i+1} \in S(G)$.
\end{enumerate}

Since each property $Q_i, i=1, 2, 3, 4$, is obtained by negation from the 
corresponding property $P_i$ (with $u, w$ replaced by $u_i, u_{i+1}$
respectively), we obtain the following corollary of Proposition \ref{ordering}.

\begin{cor}\label{macka}
No chronological interval digraph contains an asynchronous triple.
\qed
\end{cor}


For a graph $G$ to be an interval graph, there are two natural necessary 
conditions: $G$ has to be chordal (i.e., must not contain a chordless cycle of 
length greater than three), and it must not have any asteroidal triples. 
The celebrated theorem of Lekkerkerker and Boland \cite{LB} claims that 
these two conditions together are also sufficient, i.e., 
a chordal graph without asteroidal triples is an interval graph.

We have also found two necessary conditions for a digraph $G$ to be 
a chronological interval digraph: $G$ has to be clustered, and it must not 
have any asynchronous triples. It is our goal to prove that these two 
conditions together are again sufficient.

Before we proceed with the proof, we point out that neither of the two 
conditions alone is sufficient. For instance, the reflexive digraph $Y$ 
in Figure~\ref{y} is clustered and contains an asynchronous triple. Indeed,
the triple $a, b, c$ is asynchronous, since for each ordering $u < v < w$ 
of $a, b, c$, the unique path $u = u_1, u_2, \dots, u_5 = w$ in the underlying 
graph of $Y$ has, for each $i = 1, 2, \dots, 4$, the triple $u_i, v, u_{i+1}$ 
satisfy one of properties $Q_1$ or $Q_3$ above. 
Moreover, the digraph $Z$ in Figure \ref{z}, which is not clustered,
has no asynchronous triple. 
To show it does not contain an asynchronous triple, we may focus without loss 
of generality on the triples $a, b, c$ and $a, c, d$. It is easy to see that 
there is no sequence from $b$ to $c$ which satisfies the property that 
each pair of consecutive vertices with $a$ in the middle is a bad triple. 
So $a, b, c$ is not an asynchronous triple. Similarly, there is no 
such sequence from $d$ to $c$, so $a, c, d$ is not an asynchronous triple.

\begin{figure}[hbtf]
\centerline{\includegraphics[height=30mm,width=58mm]{y.eps}}
\caption{The reflexive digraph $Y$; the loops are not drawn}
\label{y}
\end{figure}

There is another obstruction we can use in place of asynchronous triples. 
It takes advantage of the special structure of clustered digraphs, and is
reminiscent of the linear ordering of max cliques, that characterizes interval
graphs \cite{FG}.

An {\em out-branching} rooted at a vertex $h$ in a digraph $G$ is a spanning 
oriented tree $T$ of $G$ in which each vertex $v \neq h$ has in-degree one (and
$h$ has in-degree zero). One of the prominent features of an out-branching $T$ 
is that there is a unique directed path in $T$ from $h$ to every vertex $v$.
For each vertex $v \neq h$, we use $v^-$ to denote the unique in-neighbour of 
$v$ in $T$. We call $v^-$ the {\em parent} of $v$ and call $v$ a {\em child} 
of $v^-$. Two vertices which have the same parent are {\em siblings}. 
If $u \neq v$ and there is a directed path in $T$ from $u$ to $v$, 
we say that $u$ is an {\em ancestor} of $v$ and that $v$ is a 
{\em descendant} of $u$ in $T$. Thus the root $h$ is an ancestor of 
every other vertex. 

%The {\em condensation} of a digraph $G$ is obtained from $G$ by replacing each
%strong component $C$ by a vertex $v_C$ and putting an edge from $v_C$ to 
%$v_{C'}$ just if $G$ has any arc from a vertex in $C$ to a vertex in $C'$.

Clustered digraphs contain special out-branchings. 
Let $G$ be a clustered digraph. Since $G$ is in-semicomplete, it has 
a unique initial strong component (i.e., having no incoming arcs from 
any other strong component).
If a strong component $C$ of $G$ has an incoming arc from a vertex $x$
in another strong component, then every vertex of $C$ is an out-neighbour of
$x$ since all vertices of $C$ have the same in-neighbourhood.
It follows that if a strong component $C$ has incoming arcs from two other
strong components $C', C''$ then there is an arc between $C'$ and $C''$.
Hence, if strong component $C$ is not initial then amongst the strong 
components that have an arc to $C$ there is a unique strong component $C^-$ 
such that any other strong component that has an arc to $C$ also has an arc to 
$C^-$.

Since $G$ is clustered, each strong component $C$ is a complete digraph and
the vertices of $C$ can be ordered, $v_1, v_2, \dots, v_k$, such that
$N^+(v_i) \subseteq N^+(v_j)$ for all $i < j$.
Note that vertices of $C$ of the same out-neighbourhood appear consecutively
in the ordering so such an ordering is unique up to relabelings of vertices of
the same out-neighbourhood. Clearly, $v_1v_2 \dots v_k$ is a hamiltonian path 
of $C$. We call it a canonical path of $C$ and $v_1$ (respectively, $v_k$)
the first (respectively, last) vertex of the path.
It is easy to see that if $C$ is not initial, then the first vertex of 
a canonical path of $C$ is an out-neighbour of the last vertex of 
a canonical path of $C^-$.
Arbitrarily choose a canonical path for each strong component.
Let $T$ be the spanning subdigraph of $G$ consisting of all arcs in canonical
paths and the arc from the last vertex of the path of $C^-$ to the first 
vertex of the path of $C$ for each strong component $C$ which is not initial. 
It is easy to see that $T$ is an out-branching of $G$ rooted at the first 
vertex of the path of the initial component.
We call $T$ a {\em canonical out-branching} of $G$. 

\begin{prp} \label{canout}
Suppose that $G$ is a clustered digraph and $T$ is a canonical out-branching of 
$G$. Then for any two vertices $u, v$ the following three properties hold:
\begin{enumerate}
\item if $u$ is an ancestor of $v$ in $T$ and $uv$ is an arc of $G$, then
      for each vertex $x$ in the unique directed path from $u$ to $v$ in $T$,
      $ux$ is an arc of $G$;
\item if $u$ is an ancestor of $v$ in $T$ and $uv$ is a symmetric arc of $G$,
      then for each vertex $x$ in the directed path $P$ from $u$ to $v$ in $T$,
      $ux$ is a symmetric arc of $G$, that is, all vertices in $P$ are in
      the same strong component of $G$; furthermore, $N^+(u) \subseteq N^+(v)$;
\item if neither of $u, v$ is an ancestor of the other in $T$, then
      there is no directed path in $G$ between $u$ and $v$.
\end{enumerate}
\end{prp}

\pf
Suppose that $u$ is an ancestor of $v$ in $T$ and $uv$ is an arc in $G$.
Let $x_1x_2 \dots x_k$ be the directed path in $T$ from $u$ to $v$.
Let $i \geq 1$ be the smallest subscript such that $x_1x_j$ is an arc of $G$ 
for each $i = j, \dots, k$. If $i > 1$, then both $x_1, x_{i-1}$ are 
in-neighbours of $x_i$. Since $G$ is in-semicomplete
there is an arc between $x_1$ and $x_{i-1}$ in $G$. The minimality of $i$
implies that $x_{i-1}x_1$ is an arc in $G$. Thus $x_1 \dots x_{i-1}x_1$ is
a directed cycle in $G$ and hence $x_1x_{i-1}$ is a symmetric arc in $G$,
a contradiction to the minimality of $i$. So $i = 1$, i.e., $T$ satisfies
property $1$. If $uv = x_1x_k$ is a symmetric arc, then $x_1x_2 \dots x_kx_1$ 
is a directed cycle in $G$. Hence $x_1x_i$ is a symmetric arc for each 
$i = 1, 2, \dots, x_k$, i.e., $T$ satisfies property $2$.

For property $3$, suppose that neither of $u, v$ is an ancestor of the other.
Let $w_1\dots w_tu_1 \dots u_r$ and $w_1\dots w_tv_1 \dots v_s$ be the unique 
paths from the root of $T$ to $u$ and $v$ respectively where
$u_i \neq v_j$ for all $1 \leq i \leq r$ and $1 \leq j \leq s$.
First we show that $w_tu_1$ is not symmetric.
Otherwise $w_t, u_1$ are in the same strong component. Since $w_t$ is
the parent of $u_1$, it is not the last vertex in the strong component
and so cannot be the parent of two children. This is a contradiction,
as it is also the parent of $v_1$. Hence $w_tu_1 \in A(G) - S(G)$.
Similarly, $w_tv_1 \in A(G) - S(G)$.

Suppose to the contrary that there is a directed path in $G$ between $u$ 
and $v$.
Without loss of generality assume $u=u_ru_{r+1} \dots u_{r+t}v_s=v$ is 
such a path. Note that the two paths $u_1\dots u_r$ and $u_{r+1}\dots u_{r+t}$
may have vertices in common (and thus $u_1\dots u_ru_{r+1} \dots u_{r+t}$
is a walk but not necessarily a path).
Note also that there is an arc (e.g., $v_{r+t}v_s$) between 
$u_1\dots u_ru_{r+1} \dots u_{r+t}$ and $v_1\dots v_s$ 
Consider such an arc joining $u_i$ and $v_j$ with the minimum sum $i+j$. 
The minimality of $i+j$ and the fact that $G$ is in-semicomplete imply
that $i=1$ and $v_ju_1$ is an arc of $G$, or $j=1$ and $u_iv_1$ is an arc 
of $G$.
In the former case $v_1 \dots v_ju_1$ is a directed path from
$v_1$ to $u_1$ and in the latter case the directed walk
$u_1 \dots u_iv_1$ contains a directed path from $u_1$ to $v_1$.
Hence there is a directed path in $G$ between $u_1$ and $v_1$.

We consider without loss of generality the case when there is a
directed path from $u_1$ to $v_1$. Let $u_1 = z_1z_2 \dots z_k = v_1$ be
such a path. Since $G$ is in-semicomplete, there is an arc between
$w_t$ and $z_{k-1}$. If $z_{k-1}w_t \in A(G)$, then the directed cycle
$w_tz_1\dots z_{k-1}w_t$ shows that all the vertices in the cycle are
in the same strong component. In particular, $w_tu_1 = w_tz_1$ is symmetric,
a contradiction. So $w_tz_{k-1} \in A(G) - S(G)$. This implies that
$w_t$ and $z_{k-1}$ can not be in the same strong component. However both
are in-neighbours of $v_1$. This contradicts the fact $w_t$ is the parent
of $v_1$.
\qed

Two vertices $x, y$ in a digraph $G$ are said to be {\em parallel} if 
there exist in $G$ two directed paths ending in $x$ and $y$, say
$x_1x_2 \dots x_a = x$ and $y_1y_2 \dots y_b = y$ where $a, b \geq 3$,
such that

\begin{itemize}
\item $x_1x_a, y_1y_b \notin A(G)$, and
\item for some $p, q$ with $1 < p \leq a$ and $1< q \leq b$,
      $x_1y_q, y_1x_p \in A(G)$ and there is no directed path in $G$ 
      between $x_p$ and $y_q$ in either direction.
\end{itemize}

\begin{figure}[hbtf]
\centerline{\includegraphics[height=38mm,width=46mm]{w.eps}}
\caption{}
\label{w}
\end{figure}

\begin{prp} \label{kora}
If a clustered digraph $G$ contains parallel vertices, then it contains
an asynchronous triple.
\end{prp}

\pf Suppose that $x, y$ are parallel vertices in $G$.
By definition there exist in $G$ directed paths $x_1x_2 \dots x_a = x$
and $y_1y_2 \dots y_b = y$, and subscripts $p$ and $q$, that satisfy
the conditions in the definition above. 

Let $T$ be a canonical out-branching of $G$. 
Then $T$ satisfies the properties of Proposition \ref{canout}.
These properties ensure that $T$ contains two directed paths from the root
such that one contains $x_1, x_p, x_a$ and the other contains $y_1, y_q, y_b$. 
Let $w_1\dots w_tu_1 \dots u_r$ and $w_1\dots w_tv_1 \dots v_s$ 
where $u_i \neq v_j$ for all $i, j$ be such two paths.
Since there is no directed path in $G$ between $x_p$ and $y_q$, we have
$x_p = u_{\alpha}$ and $y_q = v_{\beta}$ for some $\alpha$ and $\beta$.
Since there are directed paths in $G$ from $x_1$ to $y_q$ and from $y_1$ to
$x_p$, we have $x_1 = w_{\gamma}$ and $y_1 = w_{\eta}$ for some $\gamma$ and
$\eta$. If $x_a = w_i$ for some $i$, then
$x_p \dots x_a \dots w_tv_1 \dots v_{\beta}$ is a directed walk in $G$ from
$x_p$ to $y_q$ which contains a directed path from $x_p$ to $y_q$,
a contradiction to the assumption. So $x_a = u_{\alpha'}$ for some $\alpha'$.
A similar proof shows that $y_b = v_{\beta'}$ for some $\beta'$.
Since $w_{\eta}u_{\alpha}, w_{\gamma}v_{\beta} \in A(G)$, we have 
$w_{\eta}u_1,  w_{\gamma}v_1 \in A(G)$ according to 
Proposition \ref{canout}.

Assume without loss of generality that $\eta \leq \gamma$.
We claim that $w_t, u_{\alpha'}, v_{\beta'}$ form an asynchronous triple, 
which contradicts our assumption. Indeed, consider any ordering $<$ of 
$w_t, u_{\alpha'}, v_{\beta'}$.
Suppose first that $u_{\alpha'} < v_{\beta'} < w_t$. Consider the sequence
$u_{\alpha'}, u_{\alpha'-1}, \dots, u_1, w_t$. 
For each $1 \leq i \leq \alpha'-1$,
$u_{i+1}, v_{\beta'}, u_i$ is a bad triple because either 
$u_iu_{i+1} \in A(G) -S(G)$ or $u_iu_{i+1} \in S(G)$ and 
$v_{\beta'}u_i \notin S(G)$.
Since $w_tu_1 \in A(G) - S(G)$, $u_1, v_{\beta'}, w_t$ is also a bad triple.
The case $v_{\beta'} < u_{\alpha'} < w_t$ can be handled symmetrically.
Suppose next that $v_{\beta'} < w_t < u_{\alpha'}$. Consider the sequence
$v_{\beta'}, v_{\beta'-1}, \dots, v_1, u_{\alpha'}$. Note that 
$w_tv_i \notin S(G)$ for each
$i = 1, 2, \dots, \beta'$. We see as above that $v_{i+1}, w_t, v_i$ is a bad
triple for each $i = 1, 2, \dots, \beta'-1$.
Since $w_tv_1 \in A(G)-S(G)$, $v_1, w_t, u_{\alpha'}$ is also a bad triple.
The case $u_{\alpha'} < w_t < v_{\beta'}$ is symmetric.
Suppose now that $w_t < u_{\alpha'} < v_{\beta'}$. Consider the sequence
$w_t, w_{t-1}, \dots, w_{\gamma}, v_1, \dots, v_{\beta'}$.
Noting again that for each $i$, $u_{\alpha'}w_i \notin S(G)$, we see that
$w_{i+1}, u_{\alpha'}, w_i$ is a bad triple. Since $w_{\gamma}v_1 \in A(G)$ and
$w_{\gamma}u_{\alpha'} \notin A(G)$, the triple $w_{\gamma}, u_{\alpha'}, v_1$ 
is bad. A similar reasoning shows that $v_i, u_{\alpha'}, v_{i+1}$ is 
a bad triple for each $i = 1, 2, \dots, \beta'-1$.
Finally, for the case $w_t < v_{\beta'} < u_{\alpha'}$, we can use 
the sequence $w_t, w_{t-1}, \dots, w_{\eta}, u_1, \dots, u_{\alpha'}$.
We see that each consecutive pair of vertices in the sequence with
$v_{\beta'}$ in the middle forms a bad triple.
\qed 

The following corollary follows from Proposition \ref{kona}, 
Corollary \ref{macka}, and Proposition \ref{kora}.

\begin{cor} \label{kopa}
No chronological interval digraph contains parallel vertices.
\qed
\end{cor} 


\section{Characterizations}
\label{charac}

The following theorem contains all our characterizations of chronological interval 
digraphs.

\begin{tm} \label{structure}
The following statements concerning a digraph $G$ are equivalent:
\begin{description}
\item{(i)} $G$ is a chronological interval digraph;
\item{(ii)} $G$ admits a chronological ordering;
\item{(iii)} $G$ is clustered and contains no asynchronous triple;
\item{(iv)} $G$ contains no induced $Z$ and no asynchronous triple;
\item{(v)} $G$ is clustered and contains no parallel vertices.
\end{description}
\end{tm}

\pf The equivalence of $(i)$ and $(ii)$ is established in 
Proposition \ref{ordering}.
The implication $(i) \Rightarrow (iii)$ follows from Proposition \ref{kona}
and Corollary \ref{macka}. The implication $(iii) \Rightarrow (iv)$ follows 
from Corollary \ref{zz}.

To prove $(iv) \Rightarrow (v)$, 
suppose that $G$ contains no induced $Z$ and no asynchronous triple.
In view of Proposition \ref{kora}, it suffices to prove that $G$ is clustered. 
We prove it by showing that if $G$ is not clustered then it contains 
an asynchronous triple or an induced copy of $Z$. So assume that $G$ is not 
clustered. 

Suppose first that $G$ is not in-semicomplete. Then there are three
vertices $x, y, z$ such that $xz, yz \in A(G)$ but $xy \notin A(G)$ and
$yx \notin A(G)$. We claim that $x, y, z$ form an asynchronous triple in $G$.
Indeed, consider an arbitrary ordering of the three vertices.
If $x < y < z$, then for the sequence $x, z$ the triple $x, y, z$
satisfies property $Q_2$ or $Q_3$ and hence is bad. Similarly, if
$y < x < z$, then we use the sequence $y, z$.
Suppose that $x < z < y$. Then we can use the sequence $x, y$
as $x, z, y$ satisfies property $Q_1$ or $Q_4$.
A similar argument applies to the case when $y< z < x$.
Suppose that $z < x < y$. The sequence we use is $z, y$ as $z, x, y$ satisfies
property $Q_1$ or $Q_2$. The last case $z < y < x$ is similar.
Hence we may assume that $G$ is in-semicomplete.

Let $C$ be any strong component of $G$. We show by contradiction that all 
arcs in $C$ are symmetric. Suppose that $C$ contains an arc that is not
symmetric. Let $v_1v_2 \dots v_kv_1$ be a directed cycle in $C$ where
$v_1v_2$ is not symmetric. Such a cycle exists because every arc of $C$ is 
contained in a directed cycle. We may assume the cycle is chosen to be
induced in $C$. We claim that $v_1, v_2, v_3$ form 
an asynchronous triple, which contradicts the assumption.
Indeed, consider an arbitrary ordering of $v_1, v_2, v_3$.
Suppose first that $v_1 < v_2 < v_3$. Consider the sequence
$v_1, v_k, v_{k-1}, \dots, v_3$.
Then each pair of consecutive vertices with $v_2$ in the middle satisfies
property $Q_1$ or $Q_2$.
For every other ordering $u < v < w$ of $v_1, v_2, v_3$, we can use
the sequence $u, w$ as at least one of properties $Q_1, Q_2$, and $Q_3$ is
satisfied. Indeed, if $v_2 < v_1$, then $Q_1$ is satisfied.
If $v_3 < v_1 < v_2$, then $Q_1$ or $Q_2$ is satisfied.
Finally, if $v_1 < v_3 < v_2$, then $Q_3$ is satisfied.

Since $G$ is in-semicomplete but not clustered, there exist two vertices
$u, v$ in the same strong component of $G$ such that 
$N^-(u) \neq N^-(v)$ or both $N^+(u) \not\subseteq N^+(v)$ and 
$N^+(v) \not\subseteq N^+(u)$. It follows from above that the strong
component can only contain symmetric arcs and hence is complete since 
$G$ is in-semicomplete. The fact that $C$ is complete and $G$ is 
in-semicomplete implies $N^-(u) = N^-(v)$. So we have
both $N^+(u) \not\subseteq N^+(v)$ and $N^+(v) \not\subseteq N^+(u)$.
Let $u' \in N^+(u) - N^+(v)$ and $v' \in N^+(v) - N^+(u)$ be any two
vertices. It is now easy to see that $u, v, u', v'$ induce a copy of $Z$ 
in $G$.

Finally, we prove $(v) \Rightarrow (ii)$. Suppose that $G$ is clustered and 
contains no parallel vertices. Let $T$ be a canonical out-branching of $G$
rooted at $h$. 
For each ancestor-descendant pair $(u,v)$ of vertices, define $f(u,v)$ 
as follows:

\begin{tabbing}
{\hspace{1cm}} \= $f(u,v) = 0$ \= if $uv \notin A(G)$ (and 
                 $uv' \notin A(G)$ for every descendant $v'$ of $v$),\\
\> $f(u,v) = 1$ \> if $uv \in A(G)$ but 
                $uv' \notin A(G)$ for some descendant $v'$ of $v$, and \\ 
\> $f(u,v) = 2$ \> if $uv \in A(G)$ and
                $uv' \in A(G)$ for every descendant $v'$ of $v$.
\end{tabbing}

Note that $f(u,v) \geq 1$ if and only if $uv \in A(G)$ and that $f(u,v) \leq 1$
if and only $uv' \notin A(G)$ for a descendant $v'$ of $v$. 

Let $x, y$ be siblings. Clearly, $x, y$ have the same set $U$ of ancestors.
We show that either $f(u,x) \leq f(u,y)$ for all $u \in U$ or
$f(u,x) \geq f(u,y)$ for all $u \in U$.
Suppose to the contrary that $f(u,x) < f(u,y)$ and $f(u',x) > f(u',y)$ for
some $u, u' \in U$. Then $uy \in A(G)$ and $ux' \notin A(G)$ for some 
descendant $x'$ of $x$; similarly, $u'x \in A(G)$ and $u'y' \notin A(G)$ for 
some descendant $y'$ of $y$. This means that $x', y'$ are parallel in $G$,
a contradiction to our assumption.

For each vertex $v \neq h$, let $f(v) = \sum f(u,v)$ where the sum is taken 
over all ancestors $u$ of $v$. For a technical reason as seen in the next 
section, we also let $f(h) = 0$. 
It follows from the above that if $x, y$ are siblings then
$f(x) \geq f(y)$ if and only if $f(u,x) \geq f(u,y)$ for all $u \in U$.

The out-branching $T$ may now be viewed as an ordered tree in such
a way that, for any two siblings $x, y$, $x$ is left of $y$ if and only if
$f(x) \geq f(y)$.  We can then obtain a vertex ordering $<$ of $G$ by
performing a depth first search (DFS) on $T$ by starting at $h$ and always
choosing the left-most unvisited child.
We show this ordering $<$ is a chronological ordering of $G$ by verifying
the properties $P_1 - P_4$.

If $u < v$, then either $u$ is an ancestor of $v$ or the two vertices $u, v$ 
are in different branches of $T$ and in either case $vu \notin A(G)-S(G)$. 
If $u < v < w$ and $uw \in S(G)$, then $u, v, w$ are all in the same strong 
component and hence $uv, vw \in S(G)$.
Suppose that $u < v < w$ and $uw \in A(G) - S(G)$. Then $u$ is an ancestor of 
both $v$ and $w$ but not in the same strong component as $w$. 
If $v$ is also an ancestor of $w$, then $uv \in A(G)$ and when $uv \in S(G)$, 
we must have $vw \in A(G) - S(G)$ as $N^+(v) \supseteq N^+(u)$. 
On the other hand, if $v$ is not an ancestor of $w$, then $v, w$ are
in different branches of $T$. Let $x, y$ be the siblings contained 
respectively in the directed paths in $T$ from $h$ to $u, v$. 
Since $v < w$, $f(x) \geq f(y)$ and hence $f(u,x) \geq f(u,y)$. 
Since $uw \in A(G)$, we must have $uv \in A(G) - S(G)$.
Finally suppose that $u < v < w$ and $uw \notin A(G)$. 
If $vw \in S(G)$, then $N^-(v) = N^-(w)$ as $G$ is clustered.
Since $uw \notin A(G)$, $uv \notin A(G)$. Hence $uv \notin A(G)$ or 
$vw \notin S(G)$. Therefore the ordering $<$ is a chronological ordering.
\qed

To underscore the similarity with interval graphs, we mention corresponding 
similar characterizations of interval graphs: $G$ is an interval graph if 
and only if it admits a suitable ordering (corresponds to $(ii)$), if and 
only if it is chordal and contains no asteroidal triple (cf. $(iii)$), if 
and only if it contains no induced $C_4$ and no asteroidal triple (cf. $(iv)$),
if and only if it is chordal and admits a clique tree representation that is
a path (cf. $(v)$).

As noted in the first section, an undirected graph is an interval graph 
if and only if it admits an orientation that is a chronological interval 
digraph. Thus each of the above equivalent characterizations gives rise to 
a new characterization of interval graphs. 
For instance, we have the following fact.

\begin{cor}\label{pes}
A graph $G$ is an interval graph if and only if it has an orientation which is
clustered and contains no asynchronous triple.
\qed
\end{cor}


\section{A linear time algorithm for recognition and representation}

The proof of Theorem \ref{structure} suggests a linear time algorithm to decide 
whether a given reflexive digraph is a chronological interval digraph and 
to find an interval representation if one exists. 

Let $G$ be the given reflexive digraph. For the purposes of our algorithm 
we assume that $G$ is given by adjacency lists. By applying depth first search 
(DFS) we can find the strong components of $G$, ordered as 
$C_1, C_2, \dots, C_p$,
so that there is no arc from $C_j$ to $C_i$ if $i < j$, \cite{tarjan}.
We then order the vertices inside each strong component according to their 
outdegrees, so that vertices with lower outdegrees precede vertices with 
higher outdegrees. 
(Thus the first vertex in each $C_i$ has the minimum outdegree,
and the last vertex has the maximum outdegree.) This sorting can be done in
linear time because the sum of degrees is linear with respect to 
the number of edges.
We denote by $h$ the first vertex of $C_1$. For each vertex $v \neq h$, 
we define the parent $v^-$ of $v$ as follows.
Suppose $v \in C_k$, for some $k$. If $v$ is not the first vertex in $C_k$, 
then $v^-$ is the previous vertex in the ordering of the vertices of $C_k$. 
Otherwise, if $v$ is the first vertex of $C_k$, then let $j$ be 
the largest subscript with $j < k$ such that there 
is an arc from $C_j$ to $C_k$; we let $v^-$ be the last vertex in $C_j$.
Let $T$ be the digraph having vertex set $V(G)$ and having arcs $v^-v$.  
Note that $T$ is a tree rooted at $h$ in which every vertex except $h$ has
indegree one; when $G$ is a clustered digraph $T$ is a canonical out-branching 
of $G$, as defined in Section \ref{prelim}.

Next we show how to compute the value $f(v)$ for each vertex $v$.
For distinct vertices $u, v$, call $u$ an {\em ancestor} of $v$ and $v$
a {\em descendant} of $u$ if there is a directed path from $u$ to $v$ in $T$. 
Let $U_v$ be the set of all ancestors $u$ of $v$ such that $uv \in A(G)$. 
Let $F_v$ be the set of vertices $u \in U_v$ such that there is an arc from 
$u$ to each descendant of $v$.
It is easy to see that the sets $U_v$ can be computed in linear time.
Note that for each vertex $v$ that does not have a child, 
$F_v$ consists of all in-neighbours $u \neq v$ in $G$.
Also $F_v = \cap F_x - \{v\}$ where the intersection is taken over all 
children $x$ of $v$ (i.e., $x^- = v$). 
Thus the sets $F_v$ can be computed in linear time.
(Note that we maintain $U_v, F_v$ as ordered sets.)
Let $f(v) = |U_v| + |F_v|$ for each $v$. 
Again we remark that when $G$ is a chronological interval digraph $f(v)$ is 
precisely the one defined in the proof of Theorem \ref{structure}.
Hence each vertex $v$ is equipped with value $f(v)$.

We can now proceed with a DFS on $T$ beginning with root $h$ and 
always choosing an unvisited child $x$ which has the maximum value $f(x)$.
This gives us an ordering $v_1 < v_2 < \cdots < v_n$ of the vertices of $G$. 
In the case when $G$ is a chronological interval digraph, this ordering is 
a chronological ordering as shown in the previous section. 
Hence we only need to check for each vertex $v_i$ whether the out-neighbours 
and the in-neighbours of $v_i$ appear consecutively in the ordering. 
In particular, if there exist $a_i \leq i \leq b_i \leq c_i$
such that $N^-(v_i) \cap N^+(v_i) = \{v_{a_i}, v_{a_i+1}, \dots, v_{b_i}\}$ 
and $N^+(v_i) = \{v_{a_i}, v_{a_i+1}, \dots, v_{c_i}\}$ for each $i$, then
we can find a chronological interval representation of $G$ as described in
the proof of Proposition \ref{ordering}; otherwise $G$ is not a chronological 
interval digraph. It is clear that all these steps can be implemented 
in linear time. Therefore we have the following fact.

\begin{tm} \label{rr}
There is a linear time algorithm which decides whether a given reflexive 
digraph is a chronological interval digraph and finds an interval 
representation if it is.
\qed
\end{tm}

%%%%%%%% CERTIFICATION???

\begin{thebibliography}{10}

\bibitem{bhp} J. Bang-Jensen, J. Huang and E. Prisner,
In-tournament digraphs, J. Combinatorial Theory B 59 (1993) 267 - 287.

\bibitem{bl} K.S. Booth and G.S. Lueker, Testing for the consecutive ones
property, interval graphs, and graph planarity using PQ-tree algorithms,
J. Comput. System Sci. 13 (1976) 335 - 379.

\bibitem{bbl} D.E. Brown, A.H. Busch, and J.R. Lundgren,
Interval tournaments, J. Graph Theory 56 (2007) 72 - 81.

\bibitem{derek} D.G. Corneil, S. Olariu, and L. Stewart, 
The LBFS structure and the recognition of interval graphs, 
SIAM J. Discrete Math., 23 (2009) 1905 - 1953.

\bibitem{ds} S. Das and M. Sen, An interval digraph in relation to
its associated bipartite graph, Discrete Math. 122 (1993) 113 - 136.

\bibitem{malay} S. Das, P. Talukdar, M. Sen, Homogeneously
representable interval digraphs, Electronic Notes in Discrete Math. 15 (2003) 75 - 87.

\bibitem{adjusted} T. Feder, P. Hell, J. Huang, and A. Rafiey,
Adjusted interval digraphs, 
Electronic Notes in Discrete Math. 32 (2009) 83 - 91.

\bibitem{adjustedGROW} T. Feder, P. Hell, J. Huang, and A. Rafiey,
Interval graphs, adjusted interval digraphs and reflexive list homomorphisms,
Discrete Applied Mathematics 160 (2012) 697 - 707.

\bibitem{FG} D.R. Fulkerson and O.A. Gross,
Incidence matrices and interval graphs,
Pacific J. Math. 15 (1965) 835 - 855.

\bibitem{GH} P.C. Gilmore and A.J. Hoffman, 
A characterization of comparability graphs and interval graphs, 
Canadian J. Math. 16 (1964) 539 - 548. 

\bibitem{golumbic} M.C. Golumbic, Algorithmic Graph Theory and Perfect 
Graphs, Academic Press, New York, 1980.

\bibitem{h} J. Huang, Representation characterizations of 
chordal bipartite graphs,
J. Combinatorial Theory B 96 (2006) 673 - 683.

\bibitem{LB} C.G. Lekkerkerker and J.C. Boland, 
Representation of a finite graph by a set of intervals on the real line, 
Fundamenta Math. 51 (1962) 45 - 64.

\bibitem{mm} F.R. McMorris and H.M. Mulder, Subpath acyclic digraphs,
Discrete Math. 154 (1996) 189 - 201.

\bibitem{muller} H. M\"uller, Recognizing interval digraphs and 
interval bigraphs in polynomial time, 
Discrete Appl. Math. 78 (1997) 189 - 205.

\bibitem{prisner} E. Prisner, A characterization of interval catch digraphs,
Discrete Math. 73 (1989) 285 - 289.

\bibitem{sdrw} M. Sen, S. Das, A.B. Roy and D.B. West, Interval digraphs:
An analogue of interval graphs,
J. Graph Theory 13 (1989) 581 - 592.

\bibitem{ssw} M. Sen, B.K. Sanyal and D.B. West, Representing digraphs
using intervals and circular arcs,
Discrete Math. 147 (1995) 235 - 235.

\bibitem{std} M. Sen, P. Talukdar and S. Das, Chronological orderings
of interval digraphs, Discrete Math. 306 (2006) 1601 - 1609.

\bibitem{skrien} D. Skrien, Chronological orderings of interval graphs,
Discrete Applied Math. 8 (1984) 69 - 83.

\bibitem{tarjan}  R.E. Tarjan, Depth-first search and linear graph algorithms,
12th Annual Symposium on Switching and Automata Theory (SWAT 1971),
pp.114 - 121.

\bibitem{west} D.B. West, Short proofs for interval digraphs,
Discrete Math. 178 (1998) 287 - 292.

\end{thebibliography}
\end{document}
