{'fraction_non_alphanumeric': 0.06018197773774883, 'fraction_numerical': 0.017920650316382614, 'mean_word_length': 3.5108333333333333, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
The Structure of 2-Colored Best Match Graphs

Recent investigations in computational biology have focused on a family of 2-colored digraphs, called 2-colored best match graphs, which naturally arise from rooted phylogenetic trees. Actually the defining properties of such graphs are unusual, and a natural question is whether they also have properties which well fit in structural graph theory. In this paper, we prove that some underlying oriented bipartite graphs of a 2-colored best match graph are acyclic and we point out that the arising topological ordering can efficiently be used for constructing new families of 2-colored best match graphs.


Introduction
Let Γ = Γ(V, E) be a bipartite digraph without loops and multiple edges. For a vertex u of Γ, v is an out-neighbor (in-neighbor ) of u if uv (respectively vu) is an edge of Γ. The set of all out-neighbors (inneighbors) of u is denoted by N (u) and N − (u) respectively. A 2-colored best match graph (2-cBMG) is a bipartite graph such that N (u) is not empty for any u ∈ V and each of the following three properties holds for any two u, v ∈ V : Before presenting our results we point out that such digraphs are strongly related to detection of ortologous genes; see [8,10,11]. Let T be a (rooted, phylogenetic) tree with leaf set L and a surjective color-map σ : L → S for a non-empty color set S. Then y ∈ L is a best match of x ∈ L, in symbols x → y, if lca(x, y) ≺ lca(x, y ′ ) for all y ′ ∈ L with σ(y) = σ(y ′ ). Here lca stands for the last common ancestor, and the partial ordering p ≺ q occurs if q is located above p along the path connecting p with the root of T . The associated colored best match graph (cBMG) is the directed graph on the vertex set L where the arcs are the ordered pairs xy with x → y and x = y. It is a colored digraph with color map σ. If a colored digraph G(T, σ) is isomorphic to the cBMG associated to the rooted tree T , then T is said to explain the vertex-colored graph (G, σ). In a cBMG, there is natural equivalence relation∼ where x∼y if x and y have the same out-neighbors and in-neighbors. In particular, x∼y implies that N (x) = N (y) but the converse is not always true. In the study of best match graphs, the most important case is |S| = 2, since all cBMGs have induced subgraphs which are 2-cBMGs; see [8,Theorem 9]. The axiomatization of the concept of a colored best much graph is due to the authors of the pioneering work [8] who showed that a 2-cBMG can equivalently be defined as a certain bipartite graph Γ(V, E). In fact, for a connected 2-colored digraph with at least one out-neighbor for each of its vertex, [8,Theorem 4] states that there exists a (rooted phylogenetic) tree T explaining (G, σ) if and only if (G, σ) has properties N1,N2, and N3.
It should be noticed however that N1 and N3 had not been considered in the literature on graph theory until the discovery of their links to evolutionary relatedness via phylogenetic trees. N2 was introduced, but only marginally studied, under the name "bi-transitive" property in the preprint [6].
This gives a motivation to consider graph-theoretic properties of "structural type" in digraphs satisfying at least one property between N1,N2, and N3. We are mostly concerned with bi-transitivity, and our contributions are stated and proven in Section 3. It turns out that our results on circuits and paths fit in well with classical works in graph theory dating back to 1980's. In the discussion in Section 3 we point out two important structural properties of bi-transitive digraphs, namely they has a long path, and some of the underlying oriented digraphs are acyclic. If we assume that N1 and N3 also hold then our results can be refined, but it remains unclear how deeply N3 can affect the structure of the digraph.
Since acyclic digraphs have topological ordering, the structure of a 2-cBMG can be locally investigated; see Section 4. Especially, the behavior of maximal and minimal vertices uncovers several new properties which can also be used as an efficient tool in classifying smaller 2-cBMGs; see Section 5.

Background on digraphs and their paths and circuits
In this paper Γ stands for a digraph without loops and multiple edges. With the usual notation, V is its vertex-set, E is its edge-set where for u, v ∈ V , the edge with tail u and head v is denoted by uv or [u, v]. A symmetric edge is a pair such that uv, vu ∈ E. A digraph Γ with vertex set {1, . . . , n} is denoted by Γ : . . , [i r , j r ]}. As in [9], Γ is called sink-free if each of its vertices has at least one out-neighbor.
A bipartite digraph Γ = Γ(V, E) is a digraph whose vertices can be divided into two disjoint sets V 1 and V 2 such that every edge connects a vertex in V 1 to one in V 2 . The two sets V 1 and V 2 may be thought of as a coloring of the graph with two colors where a coloring is a labeling of the vertices with the two colors such that no two vertices sharing the same edge have the same color. We will refer to V 1 and V 2 as the color classes. A bipartite graph is balanced if For an ordered pair of vertices (u, v) of Γ, v is strongly connected to u, if there exists a directed walk u = u 0 → u 1 → u 2 → · · · → u m → u m+1 = v such that u i u i+1 is an edge of Γ for every 0 ≤ i ≤ m. The length of the directed walk is the number of edges in it, i.e. m + 1. A directed trail is a directed walk in which all edges are distinct. A directed path is a directed trail in which all vertices are distinct. A directed circuit is a non-empty directed trail in which the first and last vertices are repeated. A directed cycle is a directed trail in which all vertices but the first and last are distinct. Two vertices u and v in Γ are independent if uv ∈ E and vu ∈ E, i.e. v ∈ N (u) and u ∈ N (v). Any two equivalent vertices u and v of Γ are independent, otherwise u ∈ N (v) = N (u) would imply that uu ∈ E contradicting the assumption that Γ has no loops. If Γ is sink-free, then any two equivalent vertices have the same color as they share a common out-neighbour.
A digraph is oriented if uv ∈ E implies vu ∈ E. We can derive a new graphΓ from a bipartite digraph Γ by keeping the same vertex set but eliminating all symmetric edges from Γ such that if for some u, v ∈ V both uv and vu are edges in Γ, then we keep exactly one of them. We stress thatΓ may have some vertex without out-neighbor, although it cannot contain isolated vertices. Clearly,Γ is an oriented bipartite graph, and we call it an underlying oriented digraph of Γ. In the special case where uv ∈Γ if and only if u ′ v ′ ∈Γ for any u ′∼ u and v ′∼ v,Γ is called a∼ consistent underlying oriented digraph of Γ.
is a bitournament if for any two vertices u, v ∈ V with different colors, either uv ∈ E or vu ∈ E. An oriented digraph has a topological vertex ordering if its vertices can be labeled u 1 , u 2 , . . . , u n such that for any edge maximality for vertices is defined analogously. A sufficient condition for an oriented digraph to have a topological ordering is to be acyclic, that is, there is no directed cycle in the digraph; see [6]. Acyclic oriented digraphs are odd-even graphs; see [6,Theorem 3.4] and [13]. For a pair (A, O) where A is a finite set of non-negative even integers and O is a set a positive odd integers, the associated odd-even oriented digraph G A (O) on vertex-set A has edge-set E with ab ∈ E when both 1 2 (a + b) and , a ∈ A} and V 2 = {a|a ≡ 2 (mod 4)|, a ∈ A}. Acyclic digraphs are also relevant in genomics data processing; see [19].
The equivalence relation∼ gives rise to the quotient graph Γ ′ (V ′ , E ′ ) whose vertices are the equivalence classes and edges are defined as follows. Let u ′ and v ′ be two vertices of Γ ′ , then the ordered pair u ′ v ′ is in E ′ whenever uv ∈ E for every u ∈ u ′ and v ∈ v ′ . In other words, v ′ ∈ N (u ′ ) if and only if v ∈ N (u) for every u ∈ u ′ and v ∈ v ′ . One of the main properties of Γ ′ is that it contains no two equivalent vertices. Several properties are shared between Γ and its quotient Γ ′ such as connectivity and being bipartite; see [14]. Furthermore, letΓ be a∼ consistent underlying oriented digraph of Γ with edge set F . The subgraph ∆ of Γ ′ with edges u ′ v ′ where uv ∈ F for every u ∈ u ′ and v ∈ v ′ is an underlying oriented graph of Γ ′ . IfΓ has a nontrivial cycle, then ∆ also does. Therefore, if ∆ is acyclic, thenΓ is also acyclic.
With the above notation, the defining properties of a 2-cBMG can be restated as follows. A 2-cMBG is a bipartite digraph with the following properties: N1: if u and v are two independent vertices, then there exist no vertices w, t such that ut, vw, tw ∈ E.
N3: for any two vertices u, v with a common out-neighbor, if there exists no vertex w such that either uw, wv ∈ E, or vw, wu ∈ E, then they have the same in-neighbors and either all out-neighbors of u are also out-neighbors of v or all out-neighbors of v are also out-neighbors of u.
In a recent manuscript [20], 2-cBMGs are characterized as 2-colored digraphs containing no subgraph isomorphic to any of the following digraphs: • a bipartite graph on four vertices x 1 , x 2 , y 1 , y 2 with color classes {x 1 , x 2 } and {y 1 , y 2 } such that if x 1 y 1 , y 2 x 2 , y 1 x 2 ∈ E, then x 1 y 2 ∈ E.
Several papers give sufficient conditions for bipartite digraphs, in terms of the number of edges, to have cycles and paths with specified properties. These conditions can be viewed as digraph versions or variants of similar conditions on undirected bipartite graphs which were widely studied since the 1980's; see [1,2,3,4,6,5,12,16,17,18,21,22,23]. We recall those which are related to the present investigation. The references are [1,2,4,16,22].
be an oriented bipartite digraph whose vertex in-degree is at least h ≥ 0 and out-degree is at least k ≥ 0 for all vertices. Then Γ(V, E) contains either a directed cycle of length at least 2(k + h) or a directed path of length at least 2(k + h) + 3.
contains two vertex-disjoint directed cycles of lengths 2n 1 and 2n 2 , respectively, for any positive integer partition n = n l + n 2 .
A nice example of a bi-transitive bitournament arises from arithmetic, see [6]. For a nonempty subset S of natural numbers, let Γ S (S, E) be the digraph with vertex set S such that uv ∈ E if u < v and u and v have opposite parity. If U consists of all even numbers in S while V consists of all odd numbers in S, then Γ S (S, E) is bi-transitive bitournament. The importance of this example is due to the following characterization; see [6, Theorem 2.5].
Result 2.4. Let Γ(V, E) be a bitournament. Then the following properties are equivalent.
for some nonempty subset S of natural numbers.
Bi-transitive bitournaments are examples of 2-cBMGs where both N1 and N3 hold trivially. Also, Γ is a strongly connected 2-cBMG if and only if any underlying oriented digraph of Γ is a bitournament.

Paths and circuits in bi-transitive digraphs
In this section ∆ = ∆(V, E) denotes a bi-transitive bipartite digraph. Our goal is to prove several results, see Corollary and Proposition 3.4, 3.18, and 3.19, which will be useful for the study of 2-cBMGs.
To show claim (ii), take any vertex u 1 from N − (v 1 ). Then u 1 v 1 is and edge of ∆. Since v 1 u 2 is also an edge of ∆, this yields that the triple (u 1 , u 2 , v 1 ) satisfies the hypothesis of Lemma 3.1.
Lemma 3.2. Let v 1 and v 2 be distinct vertices of ∆ with the same color. If there exist u 1 , u 2 (not necessarily distinct) vertices in ∆ such that the edge set ∆(E) of ∆ has property

1)
then v 1 and v 2 are equivalent vertices of ∆.
Proof. Obviously, the color of v 1 is different from that of u 1 and u 2 . Thus u 1 and u 2 have the same color.
From the first and the third inclusion in (3.1), Lemma 3.1 holds for (v 1 , v 2 , u 2 ). Therefore, we have . Using the second and the forth inclusions, Lemma 3.1 holds Lemma 3.3. If ∆ contains no two equivalent vertices, then ∆ has no directed circuits of length four.
Proof. By way of a contradiction, Then v 1 and v 2 , as well as u 1 and u 2 , have the same color Then (3.1) holds whenever we switch u 1 and u 2 , then the claim follows from Lemma 3.2.
We show that Lemma 3.3 is a particular case of a much stronger result.
Proposition 3.4. If ∆ contains no two equivalent vertices, then no directed circuit of ∆ has length greater than 2. In particular, every underlying directed graph of ∆ is acyclic.
Proof. Since ∆ is a bipartite graph, if a directed circuit exists, it has even length. Therefore, by way of a contradiction, Since this holds true for any i, we have . Therefore, the vertices v i are all equivalent, contradicting our hypothesis.
(i) Any∼ consistent oriented digraph of ∆ is acyclic.
(ii) If ∆ contains no two equivalent vertices, the only directed cycles of ∆ have length 2 and they are induced by symmetric edges.
Example (2.1) shows that 2-cBMGs may contain symmetric edges. With the terminology of [11], symmetric edges are the reciprocal best matches, and they model orthologous genes. Two genes belonging to two different species A and B are orthologous if their last common ancestor was the speciation event that separated the lineages of A and B. We cannot have genes u 1 , u 2 from species A and v 1 from species B such that both v 1 , u 1 and v 1 , u 2 are couples of orthologous genes. On the other hand, the 2-cBMG given in Remark 3.6 contains vertices that are the endpoint of two symmetric edges, for example 3, 4, 5, 6. Even though the definition of 2-cBMG does not exclude the existence of more symmetric edges with a common endpoint, using 2-cBMGs to improve algorithms for orthologous genes detection motivates the study of 2-cBMGs where no two symmetric edges have a common endpoint. Proof. By way of a contradiction, there are u, v 1 and v 2 vertices of ∆ such that uv 1 , v 1 u, uv 2 , v 2 u are edges of ∆. Note that v 1 = v 2 as ∆ does not have multiple edges and that u = v 1 and u = v 2 as ∆ does not have loops. Let w ∈ N (v 1 ). Then w ∈ N (N (u)) ⊆ N (N (N (v 2 ))). By N2, w ∈ N (v 2 ). Similarly, . Therefore v 1 and v 2 have the same in-and out-neighbors, contradicting our hypothesis.
As we have already observed, the 2-cBMG ∆ 10 given in (2.1) has two equivalent vertices. It may also be observed that each vertex in its color class {7, 8, 9, 10} is the endpoint of a symmetric edge. This shows that the converse of Lemma 3.8 does not hold, that is, the constraint on a 2-cBMG to contain no two equivalent vertices is stronger than that of non-existence of symmetric edges with a common endpoint. However, the following result show that Proposition 3.4 and the second claim in Corollary 3.5 remain true for 2-cBMGs free from symmetric edges with a common endpoint.
Lemma 3.9. If ∆ contains no symmetric edges with a common endpoint, then ∆ has no directed circuits of length ≥ 4.
Proof. From Proposition 3.7, if ∆ has a directed circuit of length 2n with n ≥ 2, then it contains a sub-digraph Σ isomorphic to a complete bipartite digraph on 2n vertices. This yields that a vertex of ∆ ′ is the endpoint of n symmetric edges of Σ, and hence at least n symmetric edges of ∆ contradicting our hypothesis.  Proof. By way of a contradiction, we have two directed walks u In particular, u m is reachable from u. From N1, u m ∈ N (u) ∪ N (N (u)). Therefore, either u m ∈ N (u) or u m ∈ N (N (u)). Since u and w have the same color different from the one of u m , the case u m ∈ N (N (u)) cannot actually occur. Thus u m ∈ N (u). As u m w is an edge of ∆, it turns out that w ∈ N (N (u)). The same argument applies to v, therefore w ∈ N (N (u)) ∩ N (N (v)). But this contradicts Lemma 3.11 as u and v have no common out-neighbors.
Lemma 3.13. Assume that ∆ sink-free. For any three vertices u, v and w of ∆, if u and v have the same color but have no common out-neighbors, then either u or v is not strongly connected to w.
Proof. By Lemma 3.12, we may assume that w does not have the same color of u and v. Using the same argument in the proof of Lemma 3.12, u m ∈ N (u) ∪ N (N (u)). Here u, w and u m , w are pairs of vertices of different colors, hence u m and u have the same color and the case u m ∈ N (N (u)) must occur. Therefore N2 gives w ∈ N (N (N ((u))) ⊆ N (u). The same argument applies to v, then w ∈ N (v) ∩ N (u). Thus w is an out-neighbor of both u and v, contradicting one the hypotheses.
Lemma 3.14. Let u and v be any two vertices of ∆. If u is out-dominated by v, and u is strongly connected to a vertex w of ∆, then v is also strongly connected to w.
The following lemma follows by repeatedly use of bi-transitivity. Now we show some more features of bi-transitive digraphs which also satisfies one of N1 ad N3. First we prove a consequence of N1.
Lemma 3.16. Assume that N1 holds. Let u, w ∈ V 1 and v, z ∈ V 2 be four pairwise distinct vertices such that wz is a symmetric edge. If |N (u)| = |N (v)| = 1 and uz ∈ E, then vw ∈ E.
Lemma 3.17. Let ∆ be a bi-transitive graphs which also satisfies N1. Assume that ∆ is sink-free. For any three vertices u, v and w of ∆, if u and v have different colors but they are independent, then either u or v is not strongly connected to w.
Proof. By way of a contradiction, both u and v are assumed to be strongly connected to w. W.l.g. we may suppose that w and v have the same color different from the one of u. The argument in the proof of Lemma 3.13 applied to u, w shows that w ∈ N (u), while the argument in the proof of Lemma 3.12 applied to v, w gives w ∈ N (N (v)). Therefore N (u) ∩ N (N (v)) = ∅. Then u and v are not independent by N1, contradicting one of the hypotheses.
Lemma 3.17 has the following consequence.
Proposition 3.18. Let ∆ be a bi-transitive digraph which also satisfies both N1 and N4. Let u and v be two independent vertices of ∆ with no common out-neighbor. Then, for any vertex w, either u or v is not strongly connected to w. The results reported in Section 3 show that under natural hypotheses∆ has longer directed paths. For instance, Result 2.2 yields that this occurs when k + h is big enough. In Example (2.1), whenever we take a∼ consistent oriented digraph of ∆, we always find two vertices one with no in-neighbors and the other with no out-neighbor, that is k, h = 0. Result 2.2 ensures the existence of a directed path of length 3 in∆ and hence in ∆. Actually ∆ contains the directed path 1 → 7 → 5 → 9 → 3 of length 4.

The structure of a 2-cBMG
In this section Γ stands for a (not necessarily connected) 2-cBMG.
Corollary 3.5 has the following consequence.  If v is any vertex other than w, then N1 is trivial, and N3 is also trivial unless v and w have the same color but v has no in-neighbor.
In the latter case,   Proof. (i) Since m is the last vertex inΓ, it has no out-neighbor inΓ. On the other hand, since |N (m)| ≥ 1, there exists ℓ ∈ V such that ℓ ∈ N (m). Therefore, ℓm ∈ E with ℓ < m. This shows that we removed ℓm from Γ when constructingΓ. Therefore, mℓ was an edge we kept. Thus, both ℓm and mℓ are edges of Γ, that is, ℓm is a symmetric edge. By Lemma 3.8, N (m) = {ℓ}.
(ii) Case A: There exist d, e ∈ V distinct vertices such that N (d) = N (e) = {m}. In this case, d, e and ℓ have the same color Γ. We prove that the hypotheses in N3 hold for u = d and v = e. To show that d ∩ N (N (e)) = ∅ assume on the contrary the existence of w ∈ V for which both relations d ∈ N (w) and w ∈ N (e) hold. The latter one together with N (e) = {m} yields w = m, and hence the former one reads d ∈ N (m), that is, md ∈ E. Since dm ∈ E also holds, this yields that dm is a symmetric edge. From (iii) Assume on the contrary that ℓv ∈ E. Then v and ℓ have different color, and hence v and m have the same color. Thus m ∈ N (v). Take a vertex w ∈ N (v). Then mℓ, ℓv, vw ∈ E. From the bi-transitive property of Γ, we have that mw ∈ E. Since m is the last vertex inΓ this implies that mw is a symmetric edge. From (i), w = ℓ, a contradiction, contradicting the hypothesis that m is the last vertex ofΓ.
(iv) Take v ∈ V such that ℓ < v < m, and interchange ℓ and v in the fixed topological ordering inΓ. Claim (iii) ensures that we obtain a new ordering which is still a topological ordering ofΓ. Therefore, ℓ = m − 1 can always be assumed. Finally, assume that d, as given in Claim (ii), exists. Then  Proof. To prove N1 take u, v ∈Γ. We may assume that u and v have different color. From the hypotheses in N1, we have u ∈N (v) and v ∈N (u). Then u ∈ N (v) and v ∈ N (u), and N1 applies to u and v in Γ. Therefore, Therefore, N1 holds inΓ, as well.
To prove N2 it is enough to show thatΓ is bi-transitive. Take Since the edge u 1 v 2 was not removed from Γ to obtainΓ, we also have u 1 v 2 ∈Ē and henceΓ is bi-transitive. We state a corollary of Proposition 4.5.
Corollary 4.6. Assume that Γ is a 2-cBMG which contains no two equivalent vertices. Then one of the following cases occurs. Remark 4.7.

Computational classification of small 2-cBMGs
A straightforward exhaustive search of 2-cBMGs with the use of the MAGMA Algebra package [15] is possible for 2 ≤ n ≤ 7 since all subgraphs of the complete digraphs on n vertices can be stoblue for n ≤ 7. By Remarks 4.3 and 4.9, the resulting data-base can be used for the effective construction of larger 2-cBMGs. Let n ≥ 3 be an integer. For 2 ≤ i ≤ n − 1, let K i,n−i be the complete bipartite digraph with color classes B 1 = {1, . . . i} and B 2 = {i + 1, . . . n}. Up to relabeling and interchanging B 1 with B 2 , we may assume i ≤ n/2.
• B(n, i):=set of all connected digraphs in A(n, i).
• C(n, i):=set of all digraphs in A(n, i) which contain no two equivalent vertices.
• D(n, i):=set of all digraphs in A(n, i) containing no vertex without out-neighbor.