Pith. sign in

REVIEW 1 major objections 2 minor 2 cited by

Tree-partitions and small-spread tree-decompositions

T0 review · 1 major / 2 minor · reviewed 2026-05-10 · grok-4.3

Challenge this review Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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.

desk verdict This paper refines tree-partition bounds with tree degree and size controls while proving domino treewidth is tightly Theta(k Delta^2). read the letter →

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

Marc Distel , Neel Kaul , Raj Kaul , David R. Wood This is my paper · ORCID
classification math.COcs.DM
keywords treewidthtree-partitiondominotree-decompositionchordalcompletionmaximumdegreegraphdecomposition
checked against Foundation.AbsoluteFloorClosureLogicNat
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

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.

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Δ).

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Δ²).

Watch

Extended reading notes

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Δ).

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.

Editorial extensions

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.

Reading between the lines

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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

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 · score 0.0 of 10

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.

Assumptions & free parameters 0 free parameters · 1 assumptions · 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.

assumptions (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.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Tree-partitions and small-spread tree-decompositions." pith.science (2026). https://pith.science/paper/2604.05690

@misc{pith2026260405690,
  author       = {Pith},
  title        = {Pith review of: Tree-partitions and small-spread tree-decompositions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2604.05690}},
  note         = {Machine review of arXiv:2604.05690}
}
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.

Figures

Figures reproduced from arXiv: 2604.05690 by the authors.

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 of H and … view at source ↗
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. 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, c ∈ V (T… view at source ↗
Figures from the paper (2 more)
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]
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 i…

Discussion (0). Continue with ORCID to comment.

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.

Forward citations

Cited by 2 Pith papers

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

  1. Tree-partitions of graphs with bounded tree-depth

    math.CO 2026-08 conditional novelty 7.0 of 10

    Every connected graph of tree-depth h admits a tree-partition of width at most max(1, (4h-10)Δ+1) whose indexing tree has radius at most h-1.

  2. Tree-partitions of graphs with given pathwidth

    math.CO 2026-05 unverdicted novelty 6.0 of 10

    Every graph with bounded pathwidth and maximum degree has a tree-partition of bounded width whose underlying tree has bounded pathwidth, with the pathwidth bound tight up to a constant factor.

Reference graph

Works this paper leans on

61 extracted references · 61 canonical work pages · cited by 2 Pith papers

  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

Show all 61 references
  1. [9]

    Bodlaender

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

    1998

  2. [10]

    Bodlaender

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

    1999

  3. [11]

    Bodlaender and Joost Engelfriet

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

    1997

  4. [12]

    Bodlaender and Carla Groenland

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

    2026

  5. [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 Dagst...

    2022

  6. [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

    1986

  7. [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

    2024

  8. [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

    2023

  9. [17]

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

    2008

  10. [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

    2018

  11. [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

    2016

  12. [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

    2021

  13. [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

    2005

  14. [22]

    Graph theory, vol

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

    2018

  15. [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

    1995

  16. [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

    1996

  17. [25]

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

    2022

  18. [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

    2008

  19. [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 i...

    2004

  20. [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 Note...

    2004

  21. [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

    2005

  22. [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

    2007

  23. [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

    2023

  24. [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

    2022

  25. [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

    2025

  26. [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

    2024

  27. [35]

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

    2005

  28. [36]

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

    2007

  29. [37]

    Quotient tree partitioning of undirected graphs

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

    1986

  30. [38]

    Fishburn and Raphael A

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

    1982

  31. [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 Lec...

    2016

  32. [40]

    Tree-partitions of infinite graphs

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

    1991

  33. [41]

    Harvey and David R

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

    2017

  34. [42]

    Minimal triangulations of graphs: a survey

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

    2006

  35. [43]

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

    2025

  36. [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

    2017

  37. [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

    2019

  38. [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

    2021

  39. [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

    2005

  40. [48]

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

    2024

  41. [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

    2018

  42. [50]

    On the complexity of computing treelength

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

    2010

  43. [51]

    Grid spread

    Sergey Norin . Grid spread. 2026. Manuscript

    2026

  44. [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

    2017

  45. [53]

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

    2003

  46. [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

    1970

  47. [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

    1985

  48. [56]

    Tree-chromatic number

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

    2016

  49. [57]

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

    2006

  50. [58]

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

    2009

  51. [59]

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

    2025 arXiv

  52. [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

    2007

  53. [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

    2018

Pith tools

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