Forbidden configurations and dominating bicliques in undirected 2-quasi best match graphs

Abstract

2-quasi best match graphs (2-qBMGs) are directed graphs that capture a notion of close relatedness in phylogenetics. Here, we investigate the undirected underlying graph of a 2-qBMG (un-2qBMG) and show that they contain neither a path $P_l$ nor a cycle $C_l$ of length $l\ge 6$ as an induced subgraph. This property guarantees the existence of specific vertex decompositions with dominating bicliques that provide further insights into their structure.

arXiv admin note: text overlap with arXiv:2408.09997