REVIEW 3 major objections 2 minor 13 references
Tree-partitions of graphs with bounded tree-depth
T0 review · 3 major / 2 minor · reviewed 2026-08-16 · deepseek-v4-flash
Pith's one-line read Every connected graph of tree-depth h has a tree-partition into bags of size at most (4h−10)Δ+1, arranged on a tree of radius at most h−1.
desk verdict Correct and clean tree-depth analogue of Wood's pathwidth tree-partition theorem, with two minor rigor gaps in the proof that are easy to patch. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing device is Lemma 2.2, a tree-separator lemma: for a set S of vertices in a rooted tree F and any integer ℓ≥0, it produces a separator X of size at most |S|/(ℓ+1) such that every component of F\X contains at most ℓ vertices of S, and every x∈X has at least ℓ+1 vertices of S in its subtree. In the proof this is applied with ℓ=h−3 to the set S_t of bag vertices with outside neighbors. The other central object is the anchor a_t: for every connected subgraph H of the closure of a rooted tree F, Observation 2.1 gives a unique vertex a whose subtree contains all of H, and the proof repeatedly uses the path from each separator vertex to the anchor to bound the size of the shrunken bag. The identity f_h(ℓ)−(4h−10)=(ℓ−h+4)(ℓ−h+3)/(ℓ+1) shows the chosen constant is minimal for this proof.
What would settle it
Set h=3, where the theorem predicts width at most 2Δ+1 with an indexing tree of radius at most 2. Enumerate all connected graphs on up to 12 vertices, compute tree-depth, maximum degree, and the least possible width of a T-partition over all trees T of radius at most 2; any graph with td≤3 and required width >2Δ+1 would settle the smallest open case and refute Theorem 1.3.
Extended reading notes
Core claim
On the paper's own terms, the central discovery is Theorem 1.3: for any connected graph G with td(G)=h, there exists a tree T with rad(T)≤h−1 and a T-partition of G whose width is at most max{1,(4h−10)Δ(G)+1}. The construction starts with one bag containing all vertices and, whenever a bag is too large, chooses a vertex a_t of the tree-depth witness F that anchors the bag, defines S_t as the vertices of the bag with neighbors outside it, and uses Lemma 2.2 to select a small set X_t of witness-tree vertices so that each component of F\X_t contains at most h−3 vertices of S_t. The shrunken bag is then {a_t}∪S_t together with the vertices on the paths from X_t to a_t, and each remaining component becomes a new leaf-bag. The calculation f_h(ℓ)=(h−2+ℓ)(1+(h−2)/(ℓ+1))≥4h−10, minimized at ℓ=h−3, is what forces the final constant.
Load-bearing premise
The proof assumes that the chosen cut points in the hierarchy tree are never its leaves, so each cut contributes at most h−2 extra vertices; if the only possible cut points were leaves, the claimed (4h−10)Δ+1 bound could fail.
Editorial extensions
If this is right
- Every connected graph class with bounded tree-depth and bounded maximum degree has bounded tree-partition-width, with the explicit constant (4h−10)Δ+1.
- Because a tree of radius h−1 has depth at most h, the indexing tree itself has bounded tree-depth, so the decomposition gives a shallow hierarchy rather than merely a tree-like one.
- For graphs with td(G)≤h, the earlier pathwidth theorem would give a width bound of order h²Δ; this result reduces the dependence on h to linear, at least for connected graphs.
- The recursive splitting always produces a proper subset, so the process terminates and yields the claimed bound without any further assumptions on the graph beyond connectedness and finite tree-depth.
Reading between the lines
- The constant 4h−10 is an artifact of the splitting parameter ℓ; since f_h(ℓ) has the same minimum at ℓ=h−3 and ℓ=h−4, a slightly different separator strategy could plausibly lower the constant, and the lower-bound example for h=3 is far from the upper bound.
- The same 'choose anchors, cut with a tree-separator' argument should extend to other parameters defined by bounded-height closure hierarchies, such as shrub-depth or weak tree-depth, yielding similar width bounds with the height appearing linearly.
- For disconnected graphs the statement would need adjustment: joining the component trees into one indexing tree naturally adds one to the radius, so the analogous theorem would likely require rad(T)≤h rather than h−1.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proves an analogue of Wood's pathwidth tree-partition theorem for tree-depth. Theorem 1.3 states that every connected graph G with tree-depth h admits a T-partition of width at most max{1, (4h-10)Δ(G)+1} for some tree T with radius at most h-1. The proof is inductive: a large bag B_t is split via a separator set X_t obtained from Lemma 2.2, the central part B'_t is shown to be small by Claim 1, and the remaining components inherit the invariants through Claim 3. A short example (Lemma 3.1) shows that the dependence on Δ(G) is necessary even for graphs of tree-depth 3.
Significance. The result is a natural and clean extension of Wood's recent pathwidth tree-partition theorem to the stronger parameter tree-depth, with the expected linear bound O(h Δ(G)) and a radius bound of at most h-1. The proof is essentially self-contained: Lemma 2.2 is proved in the paper, the constants are explicit and not fitted, and the lower-bound example is elementary. If the two missing justifications noted in the major comments are supplied, the theorem is correct and constitutes a solid contribution to the structural study of tree-partitions.
major comments (3)
- [3, Claim 3] The equality B'_t ∩ V(F_{a_i}) = S_t ∩ V(F_{a_i}) is asserted without proof and is not immediate from (3.3), because B'_t also contains B_t ∩ X_hat_t. This equality is load-bearing: it is what turns |S_t ∩ V(C)| ≤ ℓ into |N_G(V(C_i))| ≤ h-2+ℓ, thereby maintaining invariant (iii). Please add the missing argument: since a_i ∉ X_t (otherwise a_i ∈ X_hat_t ∩ B_t ⊆ B'_t, contradicting a_i ∈ V(C_i)), the subtree F_{a_i} is disjoint from X_t. If some vertex y ∈ B_t ∩ X_hat_t ∩ V(F_{a_i}) existed, then for some x ∈ X_t the path xF a_t would meet V(F_{a_i}); because x ∉ V(F_{a_i}), the path would have to pass through a_i, forcing a_i ∈ X_hat_t ∩ B_t ⊆ B'_t, again a contradiction. Thus the equality holds, but it must be stated and proved.
- [3, before Claim 3] The assertion that the minimum-depth vertex a_i ∈ V(C_i) satisfies V(C_i) ⊆ V(F_{a_i}) is stated without proof. It is true, but it requires an argument using connectedness of C_i and minimality of the depth of a_i: if some v ∈ C_i were outside F_{a_i}, a path in the connected graph G[C_i] from a_i to v would contain a first edge leaving V(F_{a_i}). Since edges of G go between ancestor and descendant in F, the endpoint outside V(F_{a_i}) would have to be a strict ancestor of a_i, contradicting the minimal depth of a_i. Please include this justification.
- [2, Observation 2.1] Observation 2.1 is invoked at every recursive step to define a_t, but it is only labeled 'obvious' and no proof is supplied. Please add a proof: taking a vertex a ∈ V(H) of minimum depth in F, connectedness of H and H ⊆ clos(F) imply every vertex of H is a descendant of a; uniqueness follows because if a,b ∈ V(H) satisfy V(H) ⊆ V(F_a) ∩ V(F_b), then a is a descendant of b and b is a descendant of a, so a = b.
minor comments (2)
- [3, Lemma 3.1] Since tree-partition-width is integral, the lower bound tpw(G_n) ≥ n/2 would be more naturally stated as tpw(G_n) ≥ ⌈n/2⌉.
- [3, Claim 3] The sentence 'Since F_{a_i} is contained in a component C of F_{a_t} \ X_t' should explicitly note that this uses a_i ∉ X_t; as written the reason is implicit.
Circularity Check
No circularity found: Theorem 1.3 is derived from a self-contained inductive construction using only standard definitions and Lemma 2.2, with no fitted parameters or load-bearing self-citations.
full rationale
I examined the proof of Theorem 1.3 for the specified circularity patterns. The proof starts from the hypothesis td(G) <= h, fixes a rooted tree F of height h with G subset of clos(F), and recursively constructs a T-partition. The only internal ingredients are Observation 2.1 and Lemma 2.2. Observation 2.1 follows directly from the rooted-tree closure definition, and Lemma 2.2 is proved in the paper by induction on |S|; neither imports the theorem's conclusion. Claim 1 bounds |B'_t| by algebra from |S_t| <= (h-2+ell)Delta(G), which is invariant (iii), and Claim 3 maintains that invariant using Lemma 2.2 and the construction. The constant 4h-10 arises from minimizing the explicit function f_h(ell), so it is computed, not fitted. No parameter is fitted to the target width, and no prior result by the authors is cited as load-bearing; references to Wood, Ding-Oporowski, and Distel et al. are contextual and not used to justify any proof step. I also checked for renamed-known-result or ansatz-smuggling patterns; the construction is new and its inputs are standard definitions. The skeptical observation that Claim 3's equality B'_t intersect V(F_ai) = S_t intersect V(F_ai) is asserted without proof is a rigor gap, not circularity: the equality follows from the definitions, since any x in X_t lying in V(F_ai) would put a_i in B_t intersect Xhat_t, hence in B'_t, contradicting a_i in V(C_i) subset of B_t minus B'_t. Likewise, Observation 2.1 being labeled obvious is an omitted justification, not a circular use of the theorem. Overall, the derivation chain is self-contained and non-circular.
Assumptions & free parameters
assumptions (2)
- domain assumption For any graph G with td(G) ≤ h, there exists a rooted forest F of height h with V(F) = V(G) and G ⊆ clos(F).
- standard math For a rooted tree F and a connected graph H with H ⊆ clos(F), the vertex set V(H) is contained in V(F_a) for a unique a ∈ V(H).
Cite this review
Pith. "Pith review of Tree-partitions of graphs with bounded tree-depth." pith.science (2026). https://pith.science/paper/LMWHOQWV
@misc{pith2026260812723,
author = {Pith},
title = {Pith review of: Tree-partitions of graphs with bounded tree-depth},
year = {2026},
howpublished = {\url{https://pith.science/paper/LMWHOQWV}},
note = {Machine review of arXiv:2608.12723}
}
abstract
Wood~ recently showed that every graph $G$ of pathwidth $h$ and $\Delta(G)\ge1$ admits a $T$-partition of width at most $4(h+1)^2\Delta(G)$ for some tree $T$ with $pw(T)\leq2h+1$. In this paper, we establish an analogous result for tree-depth, which is a stronger parameter than pathwidth. We prove that every connected graph with tree-depth $h$ admits a $T$-partition of width at most $\mathrm{max}\{1, (4h-10)\Delta(G)+1\}$ for some tree $T$ with $\operatorname{rad}(T)\leq h-1$.
Reference graph
Works this paper leans on
-
[1]
N. Alon, G. Ding, B. Oporowski, and D. Vertigan, Partitioning into graphs with only small components, J. Combin. Theory Ser. B , 87 (2003), 231–243
work page 2003
-
[2]
J. Barát and D. R. Wood, Notes on nonrepetitive graph colouring, Electron. J. Combin. , 15 (2008), #R99
work page 2008
-
[3]
D. Chatzidimitriou, J.-F. Raymond, I. Sau, and D. M. Thilikos, An O(log OPT)- approximation for covering and packing minor models of θr, Algorithmica, 80 (2018), 1330– 1356
work page 2018
-
[4]
G. Ding and B. Oporowski, Some results on tree decomposition of graphs, J. Graph Theory, 20 (1995), 481–499
work page 1995
- [5]
-
[6]
N. Draganić, M. Kaufmann, D. M. Correia, K. Petrova, and R. Steiner, Size-Ramsey num- bers of structurally sparse graphs, Random Structures Algorithms , 68 (2026), e70059
work page 2026
-
[7]
Halin, Tree-partitions of infinite graphs, Discrete Math
R. Halin, Tree-partitions of infinite graphs, Discrete Math. , 97 (1991), 203–217
work page 1991
- [8]
Show all 13 references
-
[9]
Liu and S.-i
C.-H. Liu and S.-i. Oum, Partitioning H-minor-free graphs into three subgraphs with no large components, J. Combin. Theory Ser. B , 128 (2018), 114–133
2018
-
[10]
Raymond and D
J.-F. Raymond and D. M. Thilikos, Recent techniques and results on the Erdős-Pósa prop- erty, Discrete Appl. Math. , 231 (2017), 25–43
2017
-
[11]
Seese, Tree-partite graphs and the complexity of algorithms, in Fundamentals of Com- putation Theory , LNCS 199, Springer, (1985), 412–421
D. Seese, Tree-partite graphs and the complexity of algorithms, in Fundamentals of Com- putation Theory , LNCS 199, Springer, (1985), 412–421
1985
-
[12]
D. R. Wood, On tree-partition-width, European J. Combin. , 30 (2009), 1245–1253
2009
-
[13]
D. R. Wood, Tree-partitions of graphs with given pathwidth, (2026), arXiv:2605.27780. 7
2026 arXiv
Reviewed August 16, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.