{"id":"arxiv/2604.20042","url":"https://arxiv.org/abs/2604.20042","tags":["math.CO","cs.DM"],"score":0,"title":"On Threshold Pairwise Compatibility Graphs","domain":"math.CO","source":"arxiv","authors":["Sheikh Azizul Hakim","Md. Shamsuzzoha Bayzid"],"reviews":0,"subject":"math.CO","summary":"Pairwise Compatibility Graphs (PCGs) form a tree-metric graph class that originated in phylogeny and has since attracted sustained interest in graph theory. Several natural generalizations have been proposed in order to overcome the expressive limitations of classical PCGs, including $k$-interval-PCGs, $k$-OR-PCGs, and $k$-AND-PCGs. In this paper, we introduce $(k,t)$-threshold-PCGs, a threshold-based framework that unifies these generalized notions: adjacency is determined by whether at least $t$ among $k$ underlying PCG predicates accept the vertex pair. We investigate the expressive power…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-04-21","reactions":{}}