Treewidth versus Hadwiger number: Graph classes with dominated balanced separators are quasi-linearly treewidth-Hadwiger bounded
math.CO
Submitted: 2026-11-10
Updated: 2026-11-10
Terminology
Sources
- On the tree-width of even-hole-free graphs
- Induced subgraphs and tree-decompositions VII. Basic obstructions in $H$-free graphs
- Induced subgraphs and tree decompositions II. Toward walls and their line graphs in graphs of bounded degree
- Complete minors and average degree -- a short proof
- Sparse Induced Subgraphs of Large Treewidth
- Treewidth, Hadwiger Number, and Induced Minors
- $k$-Blocks: a connectivity invariant for graphs
- Induced minors and subpolynomial treewidth
- Induced subgraphs and tree decompositions XV. Even-hole-free graphs with bounded clique number have logarithmic treewidth
- Dominated balanced separators in wheel-induced-minor-free graphs
- Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs
- On treewidth and maximum cliques
- Towards Tight(er) Bounds for the Excluded Grid Theorem
- Treewidth versus clique number. I. Graph classes with a forbidden structure
- Treewidth versus clique number. II. Tree-independence number
- Treewidth versus clique number. III. Tree-independence number of graphs with a forbidden structure
- Treewidth of graphs with balanced separations
- Parameters Tied to Treewidth
- Treewidth, Circle Graphs and Circular Drawings
- (Theta, triangle)-free and (even hole, $K_4$)-free graphs. Part 1 : Layered wheels
Related papers
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality