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

CREATORAnnachiara Korchmaros, Peter F. Stadler
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE22 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-11791

Browse the full library · About the Tower of Babel