Treewidth of graphs with balanced separations

2014/08/17 by Dvorak, Zdenek, Norin, Sergey · 4 citations
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1408.3869

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.

Cited by

• Dominated balanced separators in wheel-induced-minor-free graphs
• String Graphs: Product Structure and Localised Representations
• Capturing an Invisible Robber using Separators
• Tree decompositions with small width, spread, order and degree

Related

• Separation Number and Treewidth, Revisited
• Coarse Balanced Separators and Tree-Decompositions
• Parameters Tied to Treewidth
• Parameters Tied to Treewidth
• Bounds on treewidth via excluding disjoint unions of cycles