{"id":"arxiv/2602.23096","url":"https://arxiv.org/abs/2602.23096","tags":["math.CO","cs.DM"],"score":0,"title":"Simultaneous separation in bounded degree trees","domain":"math.CO","source":"arxiv","authors":["Sagi Snir","Raphael Yuster"],"reviews":0,"subject":"math.CO","summary":"It follows from a classical result of Jordan that every tree with maximum degree at most $r$ containing a vertex set labeled by $[n]$, has a single-edge cut which separates two subsets $A,B \\subset [n]$ for which $\\min\\{|A|,|B|\\} \\ge (n-1)/r$. Motivated by the tree dissimilarity problem in phylogenetics, we consider the case of separating vertex sets of {\\em several} trees: Given $k$ trees with maximum degree at most $r$, containing a common vertex set labeled by $[n]$, we ask for a single-edge cut in each tree which maximizes $min\\{|A|,|B|\\}$ where $A,B \\subset [n]$ are separated by the…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-02-26","reactions":{}}