The Graph Minor Structure Theorem, originally proven by Robertson and Seymour [JCTB, 2003], asserts that there exist functions ${f_1},{f_2}:\mathbb{N} \to {\mathbb{N}}$ such that for every non-planar graph H with t := |V (H)|, every H-minor-free graph can be obtained via the clique-sum operation from graphs which embed into surfaces where H does not embed after deleting at most f1(t) many vertices with up to at most t2− 1 many "vortices" which are of "depth" at most f2(t). In the proof presented by Robertson and Seymour the functions f1and f2are non-constructive. Kawarabayashi, Thomas, and Wollan [arXiv, 2020] found a new proof showing that f1(t),f2(t) ∈ 2poly(t). While believing that this bound was the best their methods could achieve, Kawarabayashi, Thomas, and Wollan conjectured that f1and f2can be improved to be polynomials.In this paper we confirm their conjecture and prove that f1(t),f2(t) ∈ O(t2300). Our proofs are fully constructive and yield a polynomial-time algorithm that either finds H as a minor in a graph G or produces a clique-sum decomposition for G as above.

Abstract. The circumference of a graph [Formula: see text] with at least one cycle is the length of a longest cycle in [Formula: see text]. A classic result of Birmelé [ J. Graph Theory, 43 (2003), pp. 24–25] states that the treewidth of [Formula: see text] is at most its circumference minus 1. In case [Formula: see text] is 2-connected, this upper bound also holds for the pathwidth of [Formula: see text]; in fact, even the treedepth of [Formula: see text] is upper bounded by its circumference (Briański et al. [ Treedepth vs circumference, Combinatorica, 43 (2023), pp. 659–664]). In this paper, we study whether similar bounds hold when replacing the circumference of [Formula: see text] by its cocircumference, defined as the largest size of a bond in [Formula: see text], an inclusionwise minimal set of edges [Formula: see text] such that [Formula: see text] has more components than [Formula: see text]. In matroidal terms, the cocircumference of [Formula: see text] is the circumference of the bond matroid of [Formula: see text]. Our first result is the following “dual” version of Birmelé’s theorem: The treewidth of a graph [Formula: see text] is at most its cocircumference. Our second and main result is an upper bound of [Formula: see text] on the pathwidth of a 2-connected graph [Formula: see text] with cocircumference [Formula: see text]. Contrary to circumference, no such bound holds for the treedepth of [Formula: see text]. Our two upper bounds are best possible up to a constant factor.

Abstract. Alon, Seymour, and Thomas [ J. Amer. Math. Soc., 3 (1990), pp. 801–808] proved that every [Formula: see text]-vertex graph excluding [Formula: see text] as a minor has treewidth less than [Formula: see text]. Illingworth, Scott, and Wood [ Product Structure of Graphs with an Excluded Minor, preprint, arXiv:2104.06627 , 2022] recently refined this result by showing that every such graph is a subgraph of some graph with treewidth [Formula: see text], where each vertex is blown up by a complete graph of order [Formula: see text]. Solving an open problem of Illingworth, Scott, and Wood [2022], we prove that the treewidth bound can be reduced to 4 while keeping blowups of order [Formula: see text]. As an extension of the Lipton–Tarjan theorem, in the case of planar graphs, we show that the treewidth can be further reduced to 2, which is best possible. We generalize this result for [Formula: see text]-minor-free graphs, with blowups of order [Formula: see text]. This setting includes graphs embeddable on any fixed surface.

We prove that for every nowhere dense class of graphs $\mathcal{C}$, positive integer $d$, and $\varepsilon>0$, the following holds: in every $n$-vertex graph $G$ from $\mathcal{C}$ one can find two disjoint vertex subsets $A,B\subseteq V(G)$ such that $|A|\geq (1/2-\varepsilon)\cdot n$ and $|B|=\Omega(n^{1-\varepsilon})$; and either ${dist}(a,b)\leq d$ for all $a\in A$ and $b\in B$, or ${dist}(a,b)>d$ for all $a\in A$ and $b\in B$. We also show some stronger variants of this statement, including a generalization to the setting of first-order interpretations of nowhere dense graph classes.