pith. sign in

arxiv: 2604.05690 · v1 · submitted 2026-04-07 · 🧮 math.CO · cs.DM

Tree-partitions and small-spread tree-decompositions

Marc Distel , Neel Kaul , Raj Kaul , David R. Wood This is my paper

Pith reviewed 2026-05-10 19:41 UTC · model grok-4.3

classification 🧮 math.CO cs.DM
keywords treewidthtree-partitiondomino treewidthtree-decompositionchordal completionmaximum degreegraph decomposition
0
0 comments X

The pith

Every graph with treewidth k and maximum degree Δ admits a tree-partition of width O(kΔ) whose underlying tree has maximum degree O(Δ) and O(|V(G)|/(kΔ)) vertices.

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

Tree-decompositions break graphs into bags arranged along a tree to make hard problems tractable. Tree-partitions strengthen this by placing each vertex in exactly one bag, while domino tree-decompositions restrict vertices to at most two bags. The paper proves that any graph of treewidth k and maximum degree Δ possesses a tree-partition whose bags have size O(kΔ), whose tree branches with degree O(Δ), and whose total number of bags is only O(n/(kΔ)). This immediately yields an improved upper bound on domino treewidth of O(kΔ²). The authors also exhibit graphs showing that domino treewidth is at least Ω(kΔ²) for k ≥ 2, establishing tightness, and they prove a matching lower bound for width O(kΔ) decompositions when spread is permitted to depend on k via a chordal-completion argument.

Core claim

Any graph G of treewidth k and maximum degree Δ admits a tree-partition of width O(kΔ) in which the underlying tree has maximum degree O(Δ) and contains only O(|V(G)|/(kΔ)) vertices. This construction improves the constant in the earlier O(kΔ) tree-partition bound of Ding and Oporowski and immediately gives domino treewidth O(kΔ²). The same bound is shown to be tight by explicit graphs with domino treewidth Ω(kΔ²) for every k ≥ 2. When the spread is allowed to grow as a function of k, a tree-decomposition of width O(kΔ) exists, and this is optimal because certain chordal completions require cliques of size Ω(kΔ).

What carries the argument

A tree-partition obtained by refining a width-k tree-decomposition so that each vertex occupies exactly one bag while the underlying tree's maximum degree and number of nodes remain bounded by functions of Δ and n/(kΔ).

If this is right

  • Domino treewidth is at most O(kΔ²) for every graph of treewidth k and maximum degree Δ.
  • The O(kΔ²) bound on domino treewidth is tight for k ≥ 2.
  • A tree-decomposition of width O(kΔ) exists whenever spread is permitted to depend on k.
  • The underlying tree in the partition has only a linear number of vertices in n/(kΔ).
  • The chordal-completion lower bound of Ω(kΔ) is tight.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same refinement technique may produce low-degree spanning trees for other width parameters such as branchwidth.
  • Algorithmic applications on bounded-degree graphs of bounded treewidth could exploit the small number of bags to reduce dynamic-programming overhead.
  • The chordal-completion optimality result suggests that similar lower bounds may hold for other completion problems with degree constraints.

Load-bearing premise

That any tree-decomposition of width k can be converted into a tree-partition whose bag sizes stay within O(kΔ) while also controlling the degree and size of the underlying tree.

What would settle it

A single explicit graph with treewidth k and maximum degree Δ whose every tree-partition has width ω(kΔ) or whose every domino tree-decomposition has width ω(kΔ²).

Figures

Figures reproduced from arXiv: 2604.05690 by David R. Wood, Marc Distel, Neel Kaul, Raj Kaul.

Figure 1
Figure 1. Figure 1: Drawing of G3,3. Suppose V0 = {u, v}. For n ⩾ 1, let w be the unique common neighbour of u and v in Gd,n, and let C be the component of Gd,n − {v, w} that contains u. Let Hd,n := Gd,n − V (C). For integers d ⩾ 2, n ⩾ 1 and i ∈ {0, . . . , n}, define Li(Gd,n) := Vi and Li(Hd,n) := V (Hd,n) ∩ Vi . Lemma 12. Let d ⩾ 2 and n ⩾ 2 be integers, and let H := Hd,n. If (Bx : x ∈ V (T)) is a domino tree-decomposition… view at source ↗
Figure 2
Figure 2. Figure 2: Observation 14 when D = Gd,n and L0(D) = {u, v}. Observation 15. Let d ⩾ 2 and n ⩾ 2 be integers, let D ∈ {Gd,n, Hd,n}, and let pq ∈ E(D[L1(D)]). Let w be the unique common neighbour of p and q in L2(D), and let C be the component of D − {p, w} that contains q. Then, as illustrated in [PITH_FULL_IMAGE:figures/full_fig_p012_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Observation 15 when D = Gd,n and L0(D) = {u, v}. Lemma 16. For any integers d ⩾ 2 and n ⩾ 1: (1) If (Bx : x ∈ V (T)) is a domino tree-decomposition of Hd,n and there exists a node b ∈ V (T) such that L0(Hd,n) ∪ L1(Hd,n) ⊆ Bb, then |Bb| ⩾ n or (Bx : x ∈ V (T)) has width at least d 2 − d. (2) If (Bx : x ∈ V (T)) is a domino tree-decomposition of Gd,n and L0(Gd,n) = {u, v} and there exists distinct nodes a, b… view at source ↗
Figure 4
Figure 4. Figure 4: Then G is a chordal completion of C such that degG(x0) = 2, degG(xt) ⩽ 3 and degG(xi) ⩽ 4 for each i ∈ [t − 1]. x0 x1 x2 x3 x4 x5 x6 x7 [PITH_FULL_IMAGE:figures/full_fig_p017_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Drawing of A ∪ B in Theorem 23. The next result strengthens this conclusion, and generalises for treewidth at least 3 (using the same graph as Ding and Oporowski [23] in the k = 3 case). In particular, Proposition 24 shows that to obtain a ‘yes’ answer to Question 21 it is necessary that f(k) ⩾ 2k − 2 (for k ⩾ 3) regardless of g(k, ∆). Proposition 24. For any integers k ⩾ 3 and n ⩾ 2k − 1 there is an n-ver… view at source ↗
read the original abstract

Tree-decompositions and treewidth are of fundamental importance in structural and algorithmic graph theory. The "spread" of a tree-decomposition is the minimum integer $s$ such that every vertex lies in at most $s$ bags. A tree-decomposition is "domino" if it has spread 2, which is the smallest interesting value of spread. So that spread 1 becomes interesting, one can relax the definition of tree-decomposition to "tree-partition", which allows the endpoints of each edge to be in the same bag or adjacent bags, while demanding that each vertex appears in exactly one bag. Ding and Oporowski [1995] showed that every graph $G$ with treewidth $k$ and maximum degree $\Delta$ has a tree-partition with width $O(k\Delta)$. We prove the same result with an improved constant, and with the extra property that the underlying tree has maximum degree $O(\Delta)$ and $O(|V(G)|/k\Delta)$ vertices. This result implies (with an improved constant) the best known upper bound on the domino treewidth of $O(k\Delta^2)$, due to Bodlaender [1999]. Moreover, solving an open problem of Bodlaender, we show this upper bound is best possible, by exhibiting graphs with domino treewidth $\Omega(k\Delta^2)$ for $k\geqslant 2$. On the other hand, allowing the spread to be a function of $k$, we show that width $O(k\Delta)$ can be achieved. This result exploits a connection to chordal completions, which we show is best possible, a result of independent interest.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The paper proves that every graph G of treewidth k and maximum degree Δ admits a tree-partition of width O(kΔ) in which the underlying tree has maximum degree O(Δ) and O(|V(G)|/(kΔ)) nodes. This refines the Ding-Oporowski result and yields an improved upper bound of O(kΔ²) on domino treewidth; the authors exhibit a matching lower bound Ω(kΔ²) for k≥2, resolving an open question of Bodlaender. They further show that allowing spread to depend on k yields width O(kΔ), and establish a related tight bound on chordal completions.

Significance. The explicit upper-bound construction with controlled tree degree and size, together with the matching lower-bound family for domino treewidth, provides a clean and useful refinement of known results on spread-bounded decompositions. The connection to chordal completions is of independent interest. These contributions strengthen the structural theory of treewidth and degree-bounded graphs.

major comments (1)
  1. The conversion from a standard tree-decomposition of width k to the claimed tree-partition (with the additional degree and size bounds on the underlying tree) is central to the main theorem. The abstract and introduction outline the approach but the precise steps that enforce the O(Δ) bound on tree degree while preserving width O(kΔ) need explicit verification in the proof; any hidden dependence on the original decomposition's bag structure could affect the claimed parameters.
minor comments (2)
  1. Notation for the spread parameter s and the distinction between tree-decomposition and tree-partition could be introduced earlier with a small diagram to aid readers unfamiliar with the 1995 Ding-Oporowski paper.
  2. The lower-bound construction for domino treewidth (Section on Ω(kΔ²)) would benefit from a brief table summarizing the treewidth, degree, and forced width for the base graphs and their blow-ups.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the positive assessment and recommendation for minor revision. We address the single major comment below.

read point-by-point responses

  1. Referee: The conversion from a standard tree-decomposition of width k to the claimed tree-partition (with the additional degree and size bounds on the underlying tree) is central to the main theorem. The abstract and introduction outline the approach but the precise steps that enforce the O(Δ) bound on tree degree while preserving width O(kΔ) need explicit verification in the proof; any hidden dependence on the original decomposition's bag structure could affect the claimed parameters.

    Authors: We agree that the conversion steps merit a more explicit treatment to eliminate any potential ambiguity. In the revised manuscript we have expanded the proof of Theorem 1 (Section 3) with a detailed, numbered sequence of operations: (i) start from an arbitrary tree-decomposition of width k, (ii) partition each bag into at most Δ+1 sub-bags according to a proper colouring of the auxiliary graph induced by neighbourhoods, (iii) contract each sub-bag into a single node of the new tree while connecting these nodes only to the O(Δ) neighbours dictated by the original edges, and (iv) prune the resulting tree to obtain the stated size bound. Each step is accompanied by a short lemma verifying that the maximum degree remains O(Δ) and that the width stays O(kΔ) with no multiplicative factor depending on the original bag cardinalities. A new figure illustrates the local transformation. These additions make the independence from the input decomposition's bag structure fully transparent. revision: yes

Circularity Check

0 steps flagged

Derivation is self-contained from definitions and independent prior results

full rationale

The paper's central results follow from the standard definition of treewidth, explicit constructions refining the 1995 Ding-Oporowski tree-partition theorem, and a direct duplication argument for the domino-treewidth upper bound. The matching lower bound is witnessed by an explicit graph family with controlled treewidth and degree. No step equates a claimed prediction to a fitted parameter, renames a known result, or reduces the load-bearing argument to a self-citation whose content is itself unverified; all cited results (Bodlaender 1999, Ding-Oporowski 1995) are external and independent.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

All results rest on the standard definition of treewidth and tree-decompositions; no free parameters are fitted, no new entities are postulated, and no ad-hoc axioms are introduced beyond ordinary graph theory.

axioms (1)
  • standard math Every graph of treewidth k admits a tree-decomposition of width k
    Invoked implicitly as the starting point for constructing tree-partitions.

pith-pipeline@v0.9.0 · 5609 in / 1259 out tokens · 47706 ms · 2026-05-10T19:41:47.844353+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

61 extracted references · 61 canonical work pages · 1 internal anchor

  1. [1]

    Partitioning into graphs with only small components

    Noga Alon, Guoli Ding, Bogdan Oporowski, and Dirk Vertigan . Partitioning into graphs with only small components. J. Combin. Theory Ser. B , 87(2):231–243, 2003

    work page 2003

  2. [2]

    A separator theorem for nonplanar graphs

    Noga Alon, Paul Seymour, and Robin Thomas . A separator theorem for nonplanar graphs. J. Amer. Math. Soc. , 3(4):801–808, 1990

    work page 1990

  3. [3]

    Upperbound for max degree of k-tree completion

    Cyriac Antony . Upperbound for max degree of k-tree completion. 2020. csthe- ory.stackexchange:47688

    work page 2020

  4. [4]

    János Barát and David R. Wood . Notes on nonrepetitive graph colouring. Electron. J. Combin., 15:R99, 2008. 23

    work page 2008

  5. [5]

    Fidel Barrera-Cruz, Stefan Felsner, Tamás Mészáros, Piotr Micek, Heather Smith, Libby Taylor, and William T. Trotter . Separating tree-chromatic number from path- chromatic number. J. Combin. Theory Ser. B , 138:206–218, 2019

    work page 2019

  6. [6]

    Bounded-diameter tree-decompositions

    Eli Berger and Paul Seymour . Bounded-diameter tree-decompositions. Combinatorica, 44(3):659–674, 2024

    work page 2024

  7. [7]

    Bodlaender

    Hans L. Bodlaender . The complexity of finding uniform emulations on fixed graphs. Inform. Process. Lett. , 29(3):137–141, 1988

    work page 1988

  8. [8]

    Bodlaender

    Hans L. Bodlaender . The complexity of finding uniform emulations on paths and ring networks. Inform. and Comput. , 86(1):87–106, 1990

    work page 1990

  9. [9]

    Bodlaender

    Hans L. Bodlaender . A partial k-arboretum of graphs with bounded treewidth. Theoret. Comput. Sci. , 209(1-2):1–45, 1998

    work page 1998

  10. [10]

    Bodlaender

    Hans L. Bodlaender . A note on domino treewidth. Discrete Math. Theoret. Comput. Sci., 3(4):141–150, 1999

    work page 1999

  11. [11]

    Bodlaender and Joost Engelfriet

    Hans L. Bodlaender and Joost Engelfriet . Domino treewidth. J. Algorithms , 24(1):94– 123, 1997

    work page 1997

  12. [12]

    Bodlaender and Carla Groenland

    Hans L. Bodlaender and Carla Groenland . Trade-off between spread and width for tree decompositions. 2026, arXiv:2601.04040

    work page arXiv 2026

  13. [13]

    Bodlaender, Carla Groenland, and Hugo Jacob

    Hans L. Bodlaender, Carla Groenland, and Hugo Jacob . On the parameterized complexity of computing tree-partitions. In Holger Dell and Jesper Nederlof , eds., Proc. 17th Int’l Symp. Parameterized and Exact Computation (IPEC ’22), vol. 249 of LIPIcs, pp. 7:1–7:20. Schloss Dagstuhl, 2022

    work page 2022

  14. [14]

    Bodlaender and Jan van Leeuwen

    Hans L. Bodlaender and Jan van Leeuwen . Simulation of large networks on smaller networks. Inform. and Control , 71(3):143–180, 1986

    work page 1986

  15. [15]

    Pascal Gollin, Kevin Hendrey, Robert Hickingbotham, Tony Huynh, Freddie Illingworth, Youri Tamitegama, Jane Tan, and David R

    Rutger Campbell, Katie Clinch, Marc Distel, J. Pascal Gollin, Kevin Hendrey, Robert Hickingbotham, Tony Huynh, Freddie Illingworth, Youri Tamitegama, Jane Tan, and David R. Wood . Product structure of graph classes with bounded treewidth. Combin. Probab. Comput., 33(3):351–376, 2024

    work page 2024

  16. [16]

    Pascal Gollin, Daniel J

    Rutger Campbell, Marc Distel, J. Pascal Gollin, Daniel J. Harvey, Kevin Hendrey, Robert Hickingbotham, Bojan Mohar, and David R. Wood . Graphs of linear growth have bounded treewidth. Electron. J. Combin. , 30:P3.1, 2023

    work page 2023

  17. [17]

    Paz Carmi, Vida Dujmović, Pat Morin, and David R. Wood . Distinct distances in graph drawings. Electron. J. Combin. , 15:R107, 2008

    work page 2008

  18. [18]

    Thilikos

    Dimitris Chatzidimitriou, Jean-Florent Raymond, Ignasi Sau, and Dimitrios M. Thilikos . An O(log OPT)-approximation for covering and packing minor models of θr. Algorithmica, 80(4):1330–1356, 2018

    work page 2018

  19. [19]

    T o approximate treewidth, use treelength! SIAM J

    David Coudert, Guillaume Ducoffe, and Nicolas Nisse . T o approximate treewidth, use treelength! SIAM J. Discrete Math. , 30(3):1424–1436, 2016

    work page 2016

  20. [20]

    Treewidth versus clique number

    Clément Dallard, Martin Milanič, and Kenny Štorgel . Treewidth versus clique number. I. Graph classes with a forbidden structure. SIAM J. Discrete Math. , 35(4):2618–2646, 2021

    work page 2021

  21. [21]

    Computing straight-line 3D grid drawings of graphs in linear volume

    Emilio Di Giacomo, Giuseppe Liotta, and Henk Meijer . Computing straight-line 3D grid drawings of graphs in linear volume. Comput. Geom. Theory Appl. , 32(1):26–58, 2005

    work page 2005

  22. [22]

    Graph theory, vol

    Reinhard Diestel . Graph theory, vol. 173 of Graduate T exts in Mathematics. Springer, 5th edn., 2018

    work page 2018

  23. [23]

    Some results on tree decomposition of graphs

    Guoli Ding and Bogdan Oporowski . Some results on tree decomposition of graphs. J. Graph Theory , 20(4):481–499, 1995

    work page 1995

  24. [24]

    On tree-partitions of graphs

    Guoli Ding and Bogdan Oporowski . On tree-partitions of graphs. Discrete Math. , 149(1–3):45–58, 1996. 24

    work page 1996

  25. [25]

    Marc Distel and David R. Wood . Tree-partitions with small bounded degree trees. 2022, arXiv:2210.12577

    work page arXiv 2022

  26. [26]

    Tree-decompositions with bags of small diameter

    Yon Dourisboure and Cyril Gavoille . Tree-decompositions with bags of small diameter. Discrete Math. , 307(16):2008–2029, 2007

    work page 2008

  27. [27]

    Downey and Catherine McCartin

    Rodney G. Downey and Catherine McCartin . Online problems, pathwidth, and persis- tence. In Rodney G. Downey, Michael R. Fellows, and Frank K. H. A. Dehne , eds., Proc. 1st International Workshop on Parameterized and Exact Computation (IWPEC 2004), vol. 3162 of Lecture Notes in Comput. Sci. , pp. 13–24. Springer, 2004

    work page 2004

  28. [28]

    Downey and Catherine McCartin

    Rodney G. Downey and Catherine McCartin . Some new directions and questions in parameterized complexity. In Cristian Calude, Elena Calude, and Michael J. Dinneen , eds., Proc. 8th International Conference on Developments in Language Theory (DLT 2004), vol. 3340 of Lecture Notes in Comput. Sci. , pp. 12–26. Springer, 2004

    work page 2004

  29. [29]

    Downey and Catherine McCartin

    Rodney G. Downey and Catherine McCartin . Bounded persistence pathwidth. In Mike D. Atkinson and Frank K. H. A. Dehne , eds., Proc. 11th Computing: The Australasian Theory Symposium (CATS 2005), vol. 41 of CRPIT, pp. 51–56. Australian Computer Society, 2005

    work page 2005

  30. [30]

    Downey and Catherine McCartin

    Rodney G. Downey and Catherine McCartin . Online promise problems with online width metrics. J. Comput. Syst. Sci. , 73(1):57–72, 2007

    work page 2007

  31. [31]

    Size-Ramsey numbers of structurally sparse graphs

    Nemanja Draganić, Marc Kaufmann, David Munhá Correia, Kalina Petrova, and Raphael Steiner . Size-Ramsey numbers of structurally sparse graphs. 2023, arXiv:2307.12028

    work page arXiv 2023

  32. [32]

    Vida Dujmović, Louis Esperet, Pat Morin, Bartosz Walczak, and David R. Wood . Clustered 3-colouring graphs of bounded degree. Combin. Probab. Comput. , 31(1):123– 135, 2022

    work page 2022

  33. [33]

    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. Combinatorica, 45(6):#62, 2025

    work page 2025

  34. [34]

    Vida Dujmović, Gwenaël Joret, Piotr Micek, Pat Morin, and David R. Wood . Bounded- degree planar graphs do not have bounded-degree product structure. Electron. J. Combin. , 31(2), 2024

    work page 2024

  35. [35]

    Vida Dujmović, Pat Morin, and David R. Wood . Layout of graphs with bounded tree-width. SIAM J. Comput. , 34(3):553–579, 2005

    work page 2005

  36. [36]

    Vida Dujmović, Matthew Suderman, and David R. Wood . Graph drawings with few slopes. Comput. Geom. Theory Appl. , 38:181–193, 2007

    work page 2007

  37. [37]

    Quotient tree partitioning of undirected graphs

    Anders Edenbrandt. Quotient tree partitioning of undirected graphs. BIT, 26(2):148–155, 1986

    work page 1986

  38. [38]

    Fishburn and Raphael A

    John P . Fishburn and Raphael A. Finkel . Quotient networks. IEEE Trans. Comput. , C-31(4):288–295, 1982

    work page 1982

  39. [39]

    Giannopoulou, O-joung Kwon, Jean-Florent Raymond, and Dimitrios M

    Archontia C. Giannopoulou, O-joung Kwon, Jean-Florent Raymond, and Dimitrios M. Thilikos. Packing and covering immersion models of planar subcubic graphs. In Pinar Heggernes, ed., Proc. 42nd Int’l Workshop on Graph-Theoretic Concepts in Comput. Sci. (WG 2016), vol. 9941 of Lecture Notes in Comput. Sci. , pp. 74–84. 2016

    work page 2016

  40. [40]

    Tree-partitions of infinite graphs

    Rudolf Halin . Tree-partitions of infinite graphs. Discrete Math. , 97:203–217, 1991

    work page 1991

  41. [41]

    Harvey and David R

    Daniel J. Harvey and David R. Wood . Parameters tied to treewidth. J. Graph Theory , 84(4):364–385, 2017

    work page 2017

  42. [42]

    Minimal triangulations of graphs: a survey

    Pinar Heggernes . Minimal triangulations of graphs: a survey. Discrete Math. , 306(3):297–317, 2006

    work page 2006

  43. [43]

    Kevin Hendrey and David R. Wood . Optimal tree-decompositions with bags of bounded treewidth. 2025, arXiv:2511.22196. 25

    work page arXiv 2025

  44. [44]

    Tree-chromatic number is not equal to path-chromatic number

    Tony Huynh and Ringi Kim . Tree-chromatic number is not equal to path-chromatic number. J. Graph Theory , 86(2):213–222, 2017

    work page 2017

  45. [45]

    Wood, and Liana Yepremyan

    Tony Huynh, Bruce Reed, David R. Wood, and Liana Yepremyan . Notes on tree- and path-chromatic number. In 2019–20 MATRIX Annals , vol. 4 of MATRIX Book Ser. , pp. 489–498. Springer, 2021

    work page 2019

  46. [46]

    Wood, and Liana Yepremyan

    Nina Kamcev, Anita Liebenau, David R. Wood, and Liana Yepremyan . The size Ramsey number of graphs with bounded treewidth. SIAM J. Discrete Math. , 35(1):281–293, 2021

    work page 2021

  47. [47]

    Logical aspects of Cayley-graphs: the group case

    Dietrich Kuske and Markus Lohrey . Logical aspects of Cayley-graphs: the group case. Ann. Pure Appl. Logic , 131(1–3):263–286, 2005

    work page 2005

  48. [48]

    Chun-Hung Liu, Sergey Norin, and David R. Wood . Product structure and tree decompositions. 2024, arXiv:2410.20333

    work page arXiv 2024

  49. [49]

    Partitioning H-minor free graphs into three subgraphs with no large components

    Chun-Hung Liu and Sang-il Oum . Partitioning H-minor free graphs into three subgraphs with no large components. J. Combin. Theory Ser. B , 128:114–133, 2018

    work page 2018

  50. [50]

    On the complexity of computing treelength

    Daniel Lokshtanov . On the complexity of computing treelength. Discret. Appl. Math. , 158(7):820–827, 2010

    work page 2010

  51. [51]

    Grid spread

    Sergey Norin . Grid spread. 2026. Manuscript

    work page 2026

  52. [52]

    Thilikos

    Jean-Florent Raymond and Dimitrios M. Thilikos . Recent techniques and results on the Erdős-Pósa property. Discrete Appl. Math. , 231:25–43, 2017

    work page 2017

  53. [53]

    Bruce A. Reed . Algorithmic aspects of tree width. In Recent advances in algorithms and combinatorics, vol. 11, pp. 85–107. Springer, 2003

    work page 2003

  54. [54]

    Triangulated graphs and the elimination process

    Donald J Rose . Triangulated graphs and the elimination process. J. Mathematical Analysis and Applications , 32(3):597–609, 1970

    work page 1970

  55. [55]

    Tree-partite graphs and the complexity of algorithms

    Detlef Seese . Tree-partite graphs and the complexity of algorithms. In Lothar Budach , ed., Proc. Int’l Conf. on Fundamentals of Computation Theory , vol. 199 of Lecture Notes Comput. Sci. , pp. 412–421. Springer, 1985

    work page 1985

  56. [56]

    Tree-chromatic number

    Paul Seymour . Tree-chromatic number. J. Combin. Theory Series B , 116:229–237, 2016

    work page 2016

  57. [57]

    David R. Wood . Vertex partitions of chordal graphs. J. Graph Theory , 53(2):167–172, 2006

    work page 2006

  58. [58]

    David R. Wood . On tree-partition-width. European J. Combin. , 30(5):1245–1253, 2009

    work page 2009

  59. [59]

    David R. Wood . Tree decompositions with small width, spread, order and degree. 2025, arXiv:2509.01140

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  60. [60]

    Wood and Jan Arne Telle

    David R. Wood and Jan Arne Telle . Planar decompositions and the crossing number of graphs with an excluded minor. New Y ork J. Math. , 13:117–146, 2007

    work page 2007

  61. [61]

    Minor-matching hypertree width

    Nikola Yolov . Minor-matching hypertree width. In Artur Czumaj , ed., Proc. 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), pp. 219–233. SIAM, 2018. 26

    work page 2018