Excluding a rectangular grid

Cl\'ement Rambaud

REVIEW 3 major objections 5 minor 13 references

Excluding a rectangular grid

T0 review · 3 major / 5 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A class of graphs has bounded k-treedepth iff it excludes every tree-times-path T□Pℓ minor for some ℓ.

desk verdict A genuinely new excluded-minor characterization for k-treedepth, carefully proved; the stress-test worry about Claim 30.1 does not land on close reading. read the letter →

arxiv 2501.11617 v2 pith:IZHRP25T submitted 2025-01-20 math.CO cs.DM

Clément Rambaud This is my paper · ORCID

classification math.COcs.DM MSC 05C8305C75

keywords k-treedepthk-pathdepthgraphminorstreewidthtreedepthgridtreedecompositionclique-sum

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper introduces $k$-treedepth, a graph parameter that interpolates between treedepth ($k=1$) and treewidth plus one ($k$ large), and proves one excluded-minor characterization for every $k$: a class of graphs has bounded $k$-treedepth if and only if, for some fixed length $\ell$, it contains no graph of the form $T \square P_\ell$ as a minor, where $T$ is any tree on $k$ vertices and $P_\ell$ is a path. The same statement specializes to three previously separate results: paths for treedepth, ladders for $2$-treedepth, and grids for treewidth. As a corollary, every graph that avoids the $k \times \ell$ rectangular grid as a minor has $(2k-1)$-treedepth bounded by a function of $k$ and $\ell$, giving a bounded-height analogue of the Grid-Minor Theorem with a cleaner obstruction. A reader should care because the theorem replaces three ad-hoc structural results with one mechanism, and it sharpens what it means to exclude a grid of bounded height.

What carries the argument

The load-bearing objects are: $k$-dismantable tree decompositions, defined by repeatedly deleting a vertex that belongs to every bag or splitting along an adhesion of size $<k$, with $k$-treedepth equal to one plus the minimum width; $k$-ladders, graphs on $[k] \times [\ell]$ whose rows are paths and whose columns are connected, because a pigeonhole argument over the $k^{k-2}$ labelled trees on $k$ vertices converts a long enough $k$-ladder into a $T \square P_\ell$ minor; and nice pairs $(U,B)$, star-shaped decompositions of a torso in which the connectivity between subsets of $U$ inside the torso is the same as inside the original graph. The proof manufactures nice pairs from lean tree decompositions with bounded adhesion and combines them by $(<k)$-clique-sums. The Grid-Minor Theorem enters once, as a black box, to guarantee that graphs with no large $k$-ladder minor have bounded treewidth.

What would settle it

For $k=3$, the only tree on three vertices is the path $P_3$; a concrete falsifier would be an infinite family of graphs with unbounded $3$-treedepth in which $P_3 \square P_2$ is never a minor. More generally, for any fixed $k$, one may search for graphs of unbounded $k$-treedepth that avoid every $T \square P_\ell$ minor for all trees $T$ on $k$ vertices at a single fixed $\ell$; such a family would refute Theorem 1.

Watch

Extended reading notes

Core claim

Let $\mathrm{td}_k$ be the largest graph invariant satisfying: $\mathrm{td}_k(\emptyset)=0$; deleting a vertex reduces the invariant by at most one; and a $(<k)$-clique-sum (gluing two graphs along a clique of fewer than $k$ vertices) has invariant at most the maximum of the two summands. This invariant agrees with treedepth for $k=1$, with the known $2$-treedepth for $k=2$, and with treewidth plus one for $k \ge |V(G)|$. The paper's central claim is that bounded $k$-treedepth is equivalent to excluding $T \square P_\ell$ as a minor for every tree $T$ on $k$ vertices, for some fixed $\ell$. The easy direction shows that $T \square P_\ell$ itself has unbounded $k$-treedepth as $\ell$ grows. The hard direction proves that any graph avoiding all $k$-ladders of length $\ell$ (graphs whose vertex set is $[k] \times [\ell]$, with each row a path and each column connected) has $k$-treedepth bounded by a function of $k$ and $\ell$: it decomposes the graph into nice pairs using well-connected tree decompositions with adhesions below $k$, and bounds each piece recursively. Since a sufficiently long $k$-ladder contains $T \square P_\ell$ as a minor by a pigeonhole argument on labelled trees, the ladder-free hypothesis is exactly the right obstruction. Consequently, forbidding the $k \times \ell$ grid forces $(2k-1)$-treedepth to be bounded by $f(k,\ell)$, which is the paper's strengthening of the Grid-Minor Theorem for bounded-height grids.

Load-bearing premise

The hard direction of Theorem 1 takes the Grid-Minor Theorem as a black box, so the proof of bounded $k$-treedepth would collapse if that theorem were removed, and the bounds it produces inherit that theorem's non-explicit estimates.

Editorial extensions

If this is right

For $k=1$, Theorem 1 recovers the classical characterization: a minor-closed class has bounded treedepth exactly when it excludes some path $P_\ell$.
For $k=2$, it recovers the ladder theorem: bounded $2$-treedepth exactly when some $2 \times \ell$ grid is excluded.
For $k$ at least $|V(G)|$, $k$-treedepth equals treewidth plus one, so the same theorem contains the Grid-Minor Theorem.
For all $k,\ell$, graphs excluding the $k \times \ell$ grid have $(2k-1)$-treedepth at most a function of $k$ and $\ell$; this is a bounded-height strengthening of the Grid-Minor Theorem.
Bounded $k$-pathdepth is equivalent to bounded pathwidth together with bounded $k$-treedepth (Theorem 4), giving a path-decomposition analogue.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The proof only guarantees existence of $f(k,\ell)$ by importing the Grid-Minor Theorem; converting this into an explicit or polynomial bound is a natural follow-up that the paper does not attempt.
The $k$-treedepth hierarchy is likely to be a tool for other minor-monotone parameters: in particular, it should bound weak coloring numbers in minor-closed classes, extending the known role of $2$-treedepth that the paper mentions.
The Section 9 framework suggests a broader program: for any parameter built from vertex additions and $(<k)$-clique-sums, the universal obstructions should again be finitely many tree-times-path graphs; testing this on elimination distance to a forest is a concrete next experiment.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Clément Rambaud's paper proves a unified excluded-minor characterization for k-treedepth, covering treedepth (k=1), ladders (k=2), and treewidth (large k). That is the real news. The k-treedepth parameter itself is new for general k, and Theorem 1 gives the if-and-only-if with T□P_l excluded for all trees on k vertices. The corollary on bounded-height grids is a nice strengthening of Grid-Minor and follows from a genuinely new part (Section 8). The paper is well above the average arXiv submission: the proofs are detailed, the hard direction is structured through explicit lemmas, and the use of the Grid-Minor Theorem as a black box is honest and clearly stated. No circularity, no fitted parameters, no invented consistency checks. I could not machine-check everything, but I read the central induction in Theorem 29 and the machinery around nice pairs, and I did not find a load-bearing gap.

The stress-test note worried about connectivity in Claim 30.1: after choosing C_i in the torso, the proof asserts N(V_i)∩V_{i-1} is connected in G[C_i ∪ union of bags]. The note suspected this uses torso edges that are not in G. On reading, the step is valid: every torso edge between vertices of U∩B is realized in G by a path inside G[B] \ clique by condition (g3) with i=1, and those bags are included in the union. The proof is too terse here and should spell this out, but the logic works. Similarly, the disjointness of the C'_i follows from the path partition condition plus the clique property of bag intersections.

The real soft spots are minor. The abstract's statement that Theorem 1 implies the Grid-Minor Theorem 'for large values of k' is over-cooked; as the reader says, it is an asymptotic consistency statement, not a proof of Grid-Minor. That should be reworded. The bounds are astronomical because of the Grid-Minor black box and the recursive definitions; that is a caveat for applications, not a flaw. The proof of Lemma 28 is heavy, and one typo f17(k,l) appears where f17(t,l) is meant, but nothing that shakes the argument.

Who should read this: structural graph theorists working on graph minors, tree decompositions, and width parameters. It will be cited. It deserves a serious referee and, after minor revisions, publication.

Referee Report

3 major / 5 minor

Summary. The paper introduces k-treedepth td_k, a parameter interpolating between treedepth (k=1) and treewidth plus one (large k), defined as the largest graph parameter satisfying vertex deletion and (<k)-clique-sum axioms. The main result, Theorem 1, characterizes classes of bounded k-treedepth as exactly those excluding, for some ℓ, all minors of the form T □ P_ℓ where T ranges over trees on k vertices. This unifies the known path/treedepth and ladder/2-treedepth results and recovers the Grid-Minor Theorem in the large-k limit. The proof builds a theory of 'nice pairs' and torsos, proves a ladder-extraction lemma, constructs well-connected tree decompositions via a Bellenbaum-Diestel style potential argument, and then proves the main structural theorem by induction on adhesion. A corollary gives a qualitative strengthening of the Grid-Minor Theorem for bounded-height grids, and a companion theorem characterizes bounded k-pathdepth via bounded pathwidth plus bounded k-treedepth.

Significance. If the proof is correct, this is a substantial unification: it gives the first excluded-minor characterization for all k, interpolating between three central graph parameters, and it provides a new structural statement for graphs excluding rectangular grids. The paper is honest about its imported ingredients: the Grid-Minor Theorem is used as a black box, and the path decomposition lemma of Robertson-Seymour is cited with a published proof in [Erd18]. The presentation is detailed and most lemmas are proved in full. However, the current version contains a load-bearing gap in Lemma 30, where an undefined quantity t is used in the main bound, and some connectivity assertions in Claim 30.1 are only sketched. These issues are localized and likely repairable, but they prevent the central proof from being accepted as written.

major comments (3)

[Lemma 30] The statement of Lemma 30 quantifies only over k, ℓ, c, but the proof defines f30(k, ℓ, c) using an undefined positive integer t, writing '2(k-1) + t · (f16(k, ℓ) · f9(max{k, ℓ}) + 2k)'. Later the proof asserts 'for every vertex u of G, |Π_G(W_y, u)| ≤ t since t ≥ 1 and for every connected component C of G - U, N_G(V(C)) induces a clique in torso_G(U, B), and so has size at most t'. No hypothesis in Lemma 30 bounds the size of such cliques in the torso, and the torso can have arbitrarily large cliques even when G excludes a fixed k-ladder (for instance, a star with many leaves can be turned into a torso with a large clique on U ∩ B, though that particular pair may fail niceness; the point is that no such bound is proved). This t is load-bearing: the bound in part (b) of Lemma 30 depends on it, and Lemma 30 is invoked in Claim 30.1, which is then used in the proof of Theorem 29. The lemma needs an additional parameter bounding the relevant clique/projection sizes, or a proof that such a bound follows from the exclusion of k-ladders together with niceness. Without this, the main induction of Theorem 29 does not close.
[Claim 30.1] In the case ℓ' ≥ 2L, after obtaining k disjoint (V_0, V_{2L})-paths Q_1, ..., Q_k in G via Lemma 24, the proof defines C_i as the vertex set of a connected component of the torso-induced subgraph and then asserts that N_torso(V_i) ∩ V_{i-1} is connected in G[C_i ∪ ⋃ C_i], where C_i is the family of bags B intersecting C_i. This is not immediate from the definitions: a path in the torso may use an edge of the clique on U ∩ B for some B, and while niceness gives a path in G[B] between the two endpoints, one must show that all U-vertices used by that path lie in C_i and that distinct C'_i remain vertex-disjoint. The disjointness can be justified from the path-partition property together with the fact that U ∩ B is a clique in the torso, and the connectivity can be repaired using property (g3), but neither argument appears in the manuscript. Since this step is what produces the f16(k, ℓ) pairwise disjoint connected subgraphs needed to contradict the exclusion of a k-ladder, it should be proved explicitly.
[Lemma 24] In the proof of Lemma 24, the text defines G′ = torso_G(V(G) \ B, {B}). This is not the correct object: removing the whole set B also removes U ∩ B, so (U, B \ {B}) is not a good pair in that torso. The intended definition is almost certainly G′ = torso_G(V(G) \(B \ U), {B}), as used in Lemma 22 and Lemma 25. The proof of Lemma 24 should be corrected accordingly.

minor comments (5)

[Lemma 17] In the induction step of Lemma 17, the expressions 'f17(k, ℓ)' inside the proof should be 'f17(t, ℓ)' to match the function parameter t.
[Theorem 7] The sentence 'This implies that one the the paths in {Q_1, ..., Q_k} is disjoint from V(C)' contains a typo ('one the the' should be 'one of the').
[Lemma 26] The threshold 'i > 3 2 (k − 1)' is a typographical artifact and should read 'i > (3/2)(k − 1)' (and similarly elsewhere). The same applies to the occurrences of '3 2 (k − 1)' in Lemma 28 and Theorem 29.
[Lemma 33] In the proof of Lemma 33, 'for every every vertex i' is a typo, and the notation φ_i(z) in the final sequence should be checked: the indices of the moving token sequences are not always consistent with the earlier definition.
[Section 7] The sentence 'Not that S C_i and S C_j are disjoint...' should read 'Note that ...'.

Circularity Check

0 steps flagged · score 1.0 of 10

No circularity: the characterization of bounded k-treedepth is derived from internal lemmas and external theorems, not from its own conclusion.

full rationale

The paper's central Theorem 1 is established by proving the easy direction (Proposition 14) and the hard direction (Theorem 29 via Lemma 30 and Claim 30.1). The parameter tdk is defined as the largest parameter satisfying explicit axioms, and Observation 11 proves the equivalence with k-dismantable tree decompositions directly from those axioms; no part of the theorem is assumed in the definition. The hard direction is an induction on the adhesion of a tree decomposition, using nice pairs to transfer connectivity between torso and graph (Lemma 24) and Lemma 16 to forbid long k-ladders. Lemma 16 is a self-contained combinatorial extraction argument using Cayley's formula, Erdős-Szekeres, and the Robertson–Seymour Grid-Minor Theorem as an external black box. The suspected step in Claim 30.1, lifting connectivity of the sets C_i from torso to G, is exactly what the nice-pair condition (g3) and Lemma 24 provide, so it is not circular. Corollary 2 follows from Lemma 31 (a long T□P_L contains the k×ℓ grid) combined with Theorem 1, again by contraposition. The only self-citations are [HLMR24a] as inspiration for the partial tree decomposition technique, which is defined and proved in the paper, and [HLMR24b]/[DHH+24] as contextual references; none is load-bearing. Heavy reliance on the Grid-Minor Theorem is a correctness/bound concern, not circularity. No step in the derivation reduces by construction to its own input.

Assumptions & free parameters 0 free parameters · 6 assumptions · 4 invented entities

The paper introduces no free parameters fitted to data and no empirical entities. It relies on several standard external theorems, chief among them the Grid-Minor Theorem, and on a cited unpublished lemma with a published proof elsewhere. The new mathematical objects are definitions and proof machinery, not postulated physical entities.

assumptions (6)

domain assumption Grid-Minor Theorem (Robertson-Seymour, Theorem 9): every graph excluding the l×l grid has treewidth < f9(l).
Invoked in Lemma 16 to force a k×l grid when treewidth is large, in Lemma 30 to bound a hitting set via Lemma 10, and in the reduction after Theorem 29. It is an external theorem, not proved here.
standard math Menger's theorem (vertex version) equating minimum cut size with maximum number of disjoint paths.
Used in Lemmas 23-26, Lemma 30, and Claim 30.1 to construct separating sets and disjoint paths.
standard math Erdős-Szekeres theorem (Theorem 20) on monotone subsequences of permutations.
Used in Lemma 16 to align the orderings of k row paths before building a k-ladder.
standard math Cayley's formula: there are k^{k-2} labeled trees on k vertices.
Used in Observation 15 and the outline of Lemma 5 to show that a long enough k-ladder contains T□P_l for some tree T on k vertices.
standard math Helly property for subtrees of a tree (Lemma 10, attributed to Robertson-Seymour).
Used repeatedly to find a bag intersecting a family of connected subgraphs and to show that clique projections intersect.
domain assumption Existence of a lean path decomposition (Lemma 6, unpublished Robertson-Seymour, proof in Erde).
Used only in the proof of Theorem 4 for k-pathdepth, not in Theorem 1. The paper cites [Erd18] for a proof.

invented entities (4)

k-treedepth (td_k)
purpose: Largest graph parameter satisfying vertex-deletion and (<k)-clique-sum inequalities; interpolates treedepth and treewidth.
New mathematical definition (k=1,2 previously defined). It has no external falsifiable handle; its value is fixed by the defining inequalities and Observation 11.
k-pathdepth (pd_k)
purpose: Path-decomposition analogue of k-treedepth; used to state Theorem 4.
New definition introduced in this paper; internal to the proof and statements.
k-ladder
purpose: Technical intermediate structure with k rows and many connected columns; used to extract T□P_l minors.
New auxiliary graph notion used in Sections 4 and 7; it has no external interpretation.
nice pairs (U,B) and torsos
purpose: Decomposition tool ensuring connectivity transfers between a graph and its torso.
New technical notions introduced in Section 5; they are internal to the proof.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Excluding a rectangular grid." pith.science (2026). https://pith.science/paper/IZHRP25T

@misc{pith2026250111617,
  author       = {Pith},
  title        = {Pith review of: Excluding a rectangular grid},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/IZHRP25T}},
  note         = {Machine review of arXiv:2501.11617}
}

abstract

For every positive integer $k$, we define the $k$-treedepth as the largest graph parameter $\mathrm{td}_k$ satisfying (i) $\mathrm{td}_k(\emptyset)=0$; (ii) $\mathrm{td}_k(G) \leq 1+ \mathrm{td}_k(G-u)$ for every graph $G$ and every vertex $u \in V(G)$; and (iii) if $G$ is a $(<k)$-clique-sum of $G_1$ and $G_2$, then $\mathrm{td}_k(G) \leq \max \{\mathrm{td}_k(G_1),\mathrm{td}_k(G_2)\}$, for all graphs $G_1,G_2$. This parameter coincides with treedepth if $k=1$, and with treewidth plus $1$ if $k \geq |V(G)|$. We prove that for every positive integer $k$, a class of graphs $\mathcal{C}$ has bounded $k$-treedepth if and only if there is a positive integer $\ell$ such that for every tree $T$ on $k$ vertices, no graph in $\mathcal{C}$ contains $T \square P_\ell$ as a minor. This implies for $k=1$ that a minor-closed class of graphs has bounded treedepth if and only if it excludes a path, for $k=2$ that a minor-closed class of graphs has bounded $2$-treedepth if and only if it excludes as a minor a ladder (Huynh, Joret, Micek, Seweryn, and Wollan; Combinatorica, 2021), and for large values of $k$ that a minor-closed class of graphs has bounded treewidth if and only if it excludes a grid (Grid-Minor Theorem, Robertson and Seymour; JCTB, 1986). As a corollary, we obtain the following qualitative strengthening of the Grid-Minor Theorem in the case of bounded-height grids. For all positive integers $k, \ell$, every graph that does not contain the $k \times \ell$ grid as a minor has $(2k-1)$-treedepth at most a function of $k$ and $\ell$.

Figures

Figures reproduced from arXiv: 2501.11617 by the authors.

**Figure 2.** Illustration for the proof of Theorem 7. This proof already contains several of the main ideas behind the proof of Theorem 1. The general approach to bound the k-treedepth of a graph G is to decompose G as a (< k)-clique-sum of graphs G1, . . . , Gm such that for every i ∈ [m], there exists Xi ⊆ Gi of bounded size such that we can bound the k-treedepth of Gi−Xi (typically by induction). Hence a first step is to iden… view at source ↗

**Figure 3.** A tree decomposition of (G − u, S) of width at most tw(G) − 1. The blue vertex depicts u, the tree T ′ = T[{x ∈ V (T) | u ∈ Wx}] is depicted in green, and S = S x∈V (T′) Wx \ {u} is the union of the red sets. 8 [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗

Figures from the paper (12 more)

**Figure 4.** Figure 4: Illustration for the proof of Lemma 13. 13 [PITH_FULL_IMAGE:figures/full_fig_p013_4.png]

**Figure 5.** Figure 5: A 5-ladder of length 10. Since every Ci is connected, we can assume without loss of generality that they are trees. Then, using Cayley’s formula stating that there are k k−2 labelled trees on k vertices, we deduce the following observation. Observation 15. For every k,…

**Figure 6.** Figure 6: Illustration for Lemmas 17 and 19 with ℓ = 4. There is a subpath P[init(P), b] such that each Bj has a “private” interval P[aj , bj ] that contains V (Bj ) ∩ V (P[init(P), b]) and is disjoint from V (P[aj ′, bj ′]) for every j ′ ̸= j. (c) V (P[aj , bj ]) ∩ V (P[aj ′, b…

**Figure 7.** Figure 7: A good pair (U, B) in G is nice if for every B ∈ B, for every i ⩾ 0, for every Z1, Z2 ⊆ U ∩ B both of size i, there are i disjoint (Z1, Z2)- paths in G[B] \ U∩B 2 . This property implies that the maximum number of pairwise disjoint paths between two given subsets of …

**Figure 8.** Figure 8: Illustration for Item (d) in Lemma 28. Now suppose that (d) does not hold. Hence there exist x1x2 ∈ E(T) with |Wx1 ∩ Wx2 | < k, x3 ∈ NT (x2) with |Wx2 ∩ Wx3 | ⩾ k, a positive integer i, and two sets Z1, Z2 ⊆ Wx1 ∩ Wx2 both of size i, such that there are no i disjoint (…

**Figure 9.** Figure 9: Construction of D′′ in the proof of Lemma 28. 7 Graphs excluding all k-ladders of length ℓ have bounded ktreedepth In this section, we prove the “if” part of Theorem 1, that is the fact that graphs excluding all k-ladders of length ℓ as minors have bounded k-treedepth…

**Figure 10.** Figure 10: Illustration for the proof of Lemma 30. For sake of clarity, we assume here that U = V (G), and Q, B1, and B2 are drawn inside Wy, but in general this is not the case, and so Zi,y contains only the projection of B1 ∪ B2 on Wy. recall that A1 = {ri}. If y ̸= x1, let y …

**Figure 11.** Figure 11: Illustration for the proof of Claim 30.1. First we remove the set Z given by Lemma 30 to ensure that R is connected in torsoG′(U ′ , B ′ ) − V (C) for every connected component C of torsoG′(U ′ , B ′ ) − Z. Fix a connected component C of torsoG′(U ′ , B ′ ). Then, we …

**Figure 12.** Figure 12: Application of Lemma 28 in the proof of Theorem 29. This yields a tree decomposition of (torsoG(U, B), S′ 0 ) for some S ′ 0 ⊆ U containing S. For sake of clarity, the connected components of torsoG(U, B) − S ′ 0 are not depicted. We want to decompose torsoG(U, B) usi…

**Figure 13.** Figure 13: A sequence (φ1, φ2, φ3, φ4) witnessing that P5 ⊑ T, where T is the tree on 6 vertices having two internal vertices of degree 3. Informally, we place the vertices of P5 as token on the graph T, and we move them one by one in such a way that for every edge xy of P5, the…

**Figure 14.** Figure 14: Illustration for Observation 32. Using the sequence (φ1, . . . , φ4) given in [PITH_FULL_IMAGE:figures/full_fig_p040_14.png]

**Figure 15.** Figure 15: The main steps in the sequence given in the proof of Lemma [PITH_FULL_IMAGE:figures/full_fig_p041_15.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

13 extracted references · 8 canonical work pages

[6]

Kernelization for Feedback Vertex Set via Elimination Distance to a Forest

arXiv:2206.04387. [Erd18] Joshua Erde. A unified treatment of linked and lean tree-decompositions. Journal of Combinatorial Theory, Series B , 130:114–143,

work page Pith review arXiv
[8]

[Hig52] Graham Higman

arXiv:1609.09098. [Hig52] Graham Higman. Ordering by divisibility in abstract algebras. Proceedings of the London Mathematical Society, s3-2(1):326–336,

arXiv
[9]

Excluding a ladder

arXiv:2002.00496. [HLMR24a] Jędrzej Hodor, Hoang La, Piotr Micek, and Clément Rambaud. Quickly excluding an apex-forest. arXiv preprint,

work page Pith review arXiv 2002
[10]

[HLMR24b] Jędrzej Hodor, Hoang La, Piotr Micek, and Clément Rambaud

arXiv:2404.17306. [HLMR24b] Jędrzej Hodor, Hoang La, Piotr Micek, and Clément Rambaud. Weak coloring numbers of minor-closed graph classes.arXiv preprint,

arXiv
[11]

Weak coloring numbers of minor-closed graph classes

arXiv:2407.04588. [NOdM12] Jaroslav Nešetřil and Patrice Ossona de Mendez.Sparsity: Graphs, Structures, and Algorithms. Springer Berlin Heidelberg,

work page Pith review arXiv
[13]

[Ram97] Siddharthan Ramachandramurthi

arXiv:2304.14121. [Ram97] Siddharthan Ramachandramurthi. The structure and number of obstructions to treewidth. SIAM Journal on Discrete Mathematics , 10(1):146–157,

arXiv
[2016]

Polynomial Bounds for the Grid-Minor Theorem

arXiv:1305.6577. [CKL+20] Marek Cygan, Paweł Komosa, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh, and Magnus Wahlström. Randomized contractions meet lean decompositions. ACM Transactions on Algorithms , 17(1):1–30,

work page Pith review arXiv
[2018]

A unified treatment of linked and lean tree-decompositions

arXiv:1703.03756. [ES35] Paul Erdős and George Szekeres. A combinatorial problem in geometry. Compositio Mathematica, 2:463–470,

work page Pith review arXiv

Show all 13 references

[2019]

[BD02] Patrick Bellenbaum and Reinhard Diestel

arXiv:1908.05706. [BD02] Patrick Bellenbaum and Reinhard Diestel. Two short proofs concerning tree- decompositions. Combinatorics, Probability and Computing , 11(6):541–547,

1908 arXiv
[2020]

[CT21] Julia Chuzhoy and Zihan Tan

arXiv:1810.06864. [CT21] Julia Chuzhoy and Zihan Tan. Towards tight(er) bounds for the excluded grid theorem. Journal of Combinatorial Theory, Series B , 146:219–265,

arXiv
[2021]

[DHH+24] Vida Dujmović, Robert Hickingbotham, Jędrzej Hodor, Gwenaël Joret, Hoang La, Piotr Micek, Pat Morin, Clément Rambaud, and David R

arXiv:1901.07944. [DHH+24] Vida Dujmović, Robert Hickingbotham, Jędrzej Hodor, Gwenaël Joret, Hoang La, Piotr Micek, Pat Morin, Clément Rambaud, and David R. Wood. The Grid-Minor Theorem revisited. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SO...

1901 arXiv
[2023]

[PPT23b] Christophe Paul, Evangelos Protopapas, and Dimitrios M

arXiv:2304.03688. [PPT23b] Christophe Paul, Evangelos Protopapas, and Dimitrios M. Thilikos. An overview of universal obstructions for graph parameters. arXiv preprint ,

arXiv
[2024]

[Die17] Reinhard Diestel

arXiv:2307.02816. [Die17] Reinhard Diestel. Graph Theory. Springer Berlin Heidelberg,

arXiv

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.

[1] [6]

Kernelization for Feedback Vertex Set via Elimination Distance to a Forest

arXiv:2206.04387. [Erd18] Joshua Erde. A unified treatment of linked and lean tree-decompositions. Journal of Combinatorial Theory, Series B , 130:114–143,

work page Pith review arXiv

[2] [8]

[Hig52] Graham Higman

arXiv:1609.09098. [Hig52] Graham Higman. Ordering by divisibility in abstract algebras. Proceedings of the London Mathematical Society, s3-2(1):326–336,

arXiv

[3] [9]

Excluding a ladder

arXiv:2002.00496. [HLMR24a] Jędrzej Hodor, Hoang La, Piotr Micek, and Clément Rambaud. Quickly excluding an apex-forest. arXiv preprint,

work page Pith review arXiv 2002

[4] [10]

[HLMR24b] Jędrzej Hodor, Hoang La, Piotr Micek, and Clément Rambaud

arXiv:2404.17306. [HLMR24b] Jędrzej Hodor, Hoang La, Piotr Micek, and Clément Rambaud. Weak coloring numbers of minor-closed graph classes.arXiv preprint,

arXiv

[5] [11]

Weak coloring numbers of minor-closed graph classes

arXiv:2407.04588. [NOdM12] Jaroslav Nešetřil and Patrice Ossona de Mendez.Sparsity: Graphs, Structures, and Algorithms. Springer Berlin Heidelberg,

work page Pith review arXiv

[6] [13]

[Ram97] Siddharthan Ramachandramurthi

arXiv:2304.14121. [Ram97] Siddharthan Ramachandramurthi. The structure and number of obstructions to treewidth. SIAM Journal on Discrete Mathematics , 10(1):146–157,

arXiv

[7] [2016]

Polynomial Bounds for the Grid-Minor Theorem

arXiv:1305.6577. [CKL+20] Marek Cygan, Paweł Komosa, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh, and Magnus Wahlström. Randomized contractions meet lean decompositions. ACM Transactions on Algorithms , 17(1):1–30,

work page Pith review arXiv

[8] [2018]

A unified treatment of linked and lean tree-decompositions

arXiv:1703.03756. [ES35] Paul Erdős and George Szekeres. A combinatorial problem in geometry. Compositio Mathematica, 2:463–470,

work page Pith review arXiv