The Structure of 2-Colored Best Match Graphs
arXiv:2009.00447
Abstract
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.
16 pages. arXiv admin note: substantial text overlap with arXiv:2006.04100 Section 4.1 is added which contains two new propositions