Pith. sign in

REVIEW 1 cited by

Coarse Balanced Separators and Tree-Decompositions

Not yet reviewed by Pith; the record is open.

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2505.06550 v2 pith:XKX3DZKB submitted 2025-05-10 math.CO

classification math.CO
keywords graphboundedbalancedcoarsenumberseparatortreewidthballs
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
abstract

A classical result of Robertson and Seymour (1986) states that the treewidth of a graph is linearly tied to its separation number: the smallest integer $k$ such that, for every weighting of the vertices, the graph admits a balanced separator of size at most $k$. Motivated by recent progress on coarse treewidth, Abrishami, Czy\.{z}ewska, Kluk, Pilipczuk, Pilipczuk, and Rz\k{a}\.{z}ewski (2025) conjectured a coarse analogue to this result: every graph that has a balanced separator consisting of a bounded number of balls of bounded radius is quasi-isometric to a graph with bounded treewidth. In this paper, we confirm their conjecture for $K_{t,t}$-induced-subgraph-free graphs when the separator consists of a bounded number of balls of radius $1$. In doing so, we bridge two important conjectures concerning the structure of graphs that exclude a planar graph as an induced minor.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Fatness and Flatness

    math.CO 2026-07 accept novelty 7.0 of 10

    Excluding a fixed graph as a fat minor forces a metric analog of uniform quasi-wideness; this bounds scatter dimension and yields EPAS-style approximation for norm k-clustering.

Pith tools