Characterizations of undirected 2-quasi best match graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909887946031104 |
|---|---|
| author | Korchmaros, Annachiara Scholz, Guillaume E. Stadler, Peter F. |
| author_facet | Korchmaros, Annachiara Scholz, Guillaume E. Stadler, Peter F. |
| contents | Bipartite best match graphs (BMG) and their generalizations arise in mathematical phylogenetics as combinatorial models describing evolutionary relationships among related genes in a pair of species. In this work, we characterize the class of \emph{undirected 2-quasi-BMGs} (un2qBMGs), which form a proper subclass of the $P_6$-free chordal bipartite graphs. We show that un2qBMGs are exactly the class of bipartite graphs free of $P_6$, $C_6$, and the eight-vertex Sunlet$_4$ graph. Equivalently, a bipartite graph $G$ is un2qBMG if and only if every connected induced subgraph contains a ``heart-vertex'' which is adjacent to all the vertices of the opposite color. We further provide a $O(|V(G)|^3)$ algorithm for the recognition of un2qBMGs that, in the affirmative case, constructs a labeled rooted tree that ``explains'' $G$. Finally, since un2qBMGs coincide with the $(P_6,C_6)$-free bi-cographs, they can also be recognized in linear time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_03592 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Characterizations of undirected 2-quasi best match graphs Korchmaros, Annachiara Scholz, Guillaume E. Stadler, Peter F. Combinatorics Discrete Mathematics 05C75, 05C85, 92D15 Bipartite best match graphs (BMG) and their generalizations arise in mathematical phylogenetics as combinatorial models describing evolutionary relationships among related genes in a pair of species. In this work, we characterize the class of \emph{undirected 2-quasi-BMGs} (un2qBMGs), which form a proper subclass of the $P_6$-free chordal bipartite graphs. We show that un2qBMGs are exactly the class of bipartite graphs free of $P_6$, $C_6$, and the eight-vertex Sunlet$_4$ graph. Equivalently, a bipartite graph $G$ is un2qBMG if and only if every connected induced subgraph contains a ``heart-vertex'' which is adjacent to all the vertices of the opposite color. We further provide a $O(|V(G)|^3)$ algorithm for the recognition of un2qBMGs that, in the affirmative case, constructs a labeled rooted tree that ``explains'' $G$. Finally, since un2qBMGs coincide with the $(P_6,C_6)$-free bi-cographs, they can also be recognized in linear time. |
| title | Characterizations of undirected 2-quasi best match graphs |
| topic | Combinatorics Discrete Mathematics 05C75, 05C85, 92D15 |
| url | https://arxiv.org/abs/2511.03592 |