Treewidth of graphs with balanced separations
classification
🧮 math.CO
cs.DM
keywords
treewidthbalancedseparationdependenceestablisheseverygraphgraphs
read the original abstract
We prove that if every subgraph of a graph $G$ has a balanced separation of order at most $a$ then $G$ has treewidth at most $15a$. This establishes a linear dependence between the treewidth and the separation number.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.