  Evolutionary scenarios describing the evolution of a family of genes within a
collection of species comprise the mapping of the vertices of a gene tree $T$
to vertices and edges of a species tree $S$. The relative timing of the last
common ancestors of two extant genes (leaves of $T$) and the last common
ancestors of the two species (leaves of $S$) in which they reside is indicative
of horizontal gene transfers (HGT) and ancient duplications. Orthologous gene
pairs, on the other hand, require that their last common ancestors coincides
with a corresponding speciation event. The relative timing information of gene
and species divergences is captured by three colored graphs that have the
extant genes as vertices and the species in which the genes are found as vertex
colors: the equal-divergence-time (EDT) graph, the later-divergence-time (LDT)
graph and the prior-divergence-time (PDT) graph, which together form an edge
partition of the complete graph.
  Here we give a complete characterization in terms of informative and
forbidden triples that can be read off the three graphs and provide a
polynomial time algorithm for constructing an evolutionary scenario that
explains the graphs, provided such a scenario exists. We show that every EDT
graph is perfect. While the information about LDT and PDT graphs is necessary
to recognize EDT graphs in polynomial-time for general scenarios, this extra
information can be dropped in the HGT-free case. However, recognition of EDT
graphs without knowledge of putative LDT and PDT graphs is NP-complete for
general scenarios. In contrast, PDT graphs can be recognized in
polynomial-time. We finally connect the EDT graph to the alternative
definitions of orthology that have been proposed for scenarios with horizontal
gene transfer. With one exception, the corresponding graphs are shown to be
colored cographs.
