  Fitch graphs $G=(X,E)$ are digraphs that are explained by $\{\emptyset,
1\}$-edge-labeled rooted trees $T$ with leaf set $X$: there is an arc $(x,y)
\in E$ if and only if the unique path in $T$ that connects the last common
ancestor $\mathrm{lca}(x,y)$ of $x$ and $y$ with $y$ contains at least one edge
with label "1". In practice, Fitch graphs represent xenology relations, i.e.,
pairs of genes $x$ and $y$ for which a horizontal gene transfer happened along
the path from $\mathrm{lca}(x,y)$ to $y$.
  In this contribution, we generalize the concept of Fitch graphs and consider
trees $T$ that are equipped with edge-labeling $\lambda: E\to \mathcal{P}(M)$
that assigns to each edge a subset $M'\subseteq M$ of colors. Given such a
tree, we can derive a map $\varepsilon_{(T,\lambda)}$ (or equivalently a set of
not necessarily disjoint binary relations), such that $i\in
\varepsilon_{(T,\lambda)}(x,y)$ (or equivalently $(x,y)\in R_i$) with $x,y\in
X$, if and only if there is at least one edge with color $i$ from
$\mathrm{lca}(x,y)$ to $y$.
  The central question considered here: Is a given map $\varepsilon$ a Fitch
map, i.e., is there there an edge-labeled tree $(T,\lambda)$ with
$\varepsilon_{(T,\lambda)} = \varepsilon$, and thus explains $\varepsilon$?
Here, we provide a characterization of Fitch maps in terms of certain
neighborhoods and forbidden submaps. Further restrictions of Fitch maps are
considered. Moreover, we show that the least-resolved tree explaining a Fitch
map is unique (up to isomorphism). In addition, we provide a polynomial-time
algorithm to decide whether $\varepsilon$ is a Fitch map and, in the
affirmative case, to construct the (up to isomorphism) unique least-resolved
tree $(T^*,\lambda^*)$ that explains $\varepsilon$.
