{"id":"arxiv/2611.20777","url":"https://arxiv.org/abs/2611.20777","tags":["math.CO"],"score":0,"title":"Treewidth and Separation Number: An Optimal Linear Bound","domain":"math.CO","source":"arxiv","authors":["Rong Chen"],"reviews":0,"subject":"math.CO","summary":"The \\emph{separation number} $\\sn(G)$ of a graph $G$ is the smallest integer $a$ such that every subgraph $H$ of $G$ admits a separation $(A,B)$ of {\\em order} $|A\\cap B|\\le a$ whose two sides $A\\setminus B$ and $B\\setminus A$ each contain at most $2|V(H)|/3$ vertices. Dvořák and Norin proved that $\\tw(G)\\le 15\\sn(G)$ for every nonempty graph $G$. We improve the constant to its optimal value: every nonempty graph satisfies $\\tw(G)\\le 4\\sn(G)-2$. This is best possible: for every $k\\ge 2$, there is a graph $G_k$ with $\\tw(G_k)=4k+2$ and $\\sn(G_k)=k+1$.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-11-16","reactions":{}}