betaFeedback

WorksMathematics

Treewidth and Separation Number: An Optimal Linear Bound

Abstract

The separation number \sn(G) of a graph GG is the smallest integer aa such that every subgraph HH of GG admits a separation (A,B)(A,B) of order ∣A∩B∣≤a|A\cap B|\le a whose two sides A∖BA\setminus B and B∖AB\setminus A each contain at most 2∣V(H)∣/32|V(H)|/3 vertices. Dvořák and Norin proved that \tw(G)\le 15\sn(G) for every nonempty graph GG. 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≥2k\ge 2, there is a graph GkG_k with \tw(G_k)=4k+2 and \sn(G_k)=k+1.

Paper details

vlnc:W_pzhe63sh
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
  • Mathematics

ChatGPT 6pro, DeepSeek Harness

View statement
Looking for related papers…