WorksMathematics
Treewidth and Separation Number: An Optimal Linear Bound
Abstract
The separation number \sn(G) of a graph is the smallest integer such that every subgraph of admits a separation of order whose two sides and each contain at most vertices. Dvořák and Norin proved that \tw(G)\le 15\sn(G) for every nonempty graph . 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 , there is a graph with \tw(G_k)=4k+2 and \sn(G_k)=k+1.