Forbidden configurations and dominating bicliques in undirected 2-quasi best match graphs Journal: Discrete Applied Mathematics
Annachiara Korchmaros, Peter F. Stadler · 2025
Read Forbidden configurations and dominating bicliques in undirected 2-quasi best match graphs Journal: Discrete Applied Mathematics by Annachiara Korchmaros, Peter F. Stadler (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-11791.txt.
Description
Annachiara Korchmaros and Peter Stadler study the undirected form of graphs that encode close matches in family trees, in a paper from 2025. These graphs arise in phylogenetics, where they flag which species are near kin to each other. Their structure limits what patterns can appear inside them.
The pair prove that such graphs hold no induced path or cycle of length six or more. That ban is strong, since long clean rings and chains are common in general graphs. From the ban they derive vertex splits built around fully linked pairs of groups. Those splits reveal further structure and may aid algorithms that read kinship from graph data.
Catalog record
| CREATOR | Annachiara Korchmaros, Peter F. Stadler |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 22 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-11791