pith. sign in

arxiv: 2509.01140 · v3 · submitted 2025-09-01 · 🧮 math.CO · cs.DM

Tree decompositions with small width, spread, order and degree

David R. Wood This is my paper

Pith reviewed 2026-05-18 20:20 UTC · model grok-4.3

classification 🧮 math.CO cs.DM
keywords treewidthtree-decompositiongraph algorithmswidthdegreespreadorder
0
0 comments X

The pith

Every graph with treewidth k has a tree-decomposition of width at most 14k+13 in which each vertex v appears in at most deg(v)+1 bags.

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

This paper proves that tree decompositions can be constructed to keep both the bag size and the number of bags per vertex small. For any graph of treewidth k, a decomposition exists with width bounded by 14k plus 13 and with each vertex repeating in no more than one extra bag beyond its degree. The result replaces an earlier exponential dependence on k with a linear one and confirms a prior conjecture. A companion construction achieves width 3k minus 1 while keeping the average number of bags per vertex down to three. These properties are useful because many graph algorithms rely on processing the graph through a sequence of small bags, and fewer repetitions per vertex reduce computational overhead.

Core claim

The central discovery is that starting from a tree decomposition of width k, the bags can be reorganized so that the width increases only to 14k+13 while ensuring no vertex appears in more bags than its degree plus one. This linear bound on appearances improves upon the exponential bound of Ding and Oporowski and strongly establishes their conjecture. Separately, a different reorganization yields width at most 3k-1 with vertices appearing in three bags on average.

What carries the argument

Bag reorganization starting from a minimum-width tree decomposition to bound the number of times each vertex occurs across the bags.

If this is right

  • Algorithms that use dynamic programming over tree decompositions incur costs proportional to the number of appearances of each vertex.
  • The linear bound allows the total size of the decomposition to be controlled in terms of the sum of degrees.
  • The second result shows a trade-off where smaller width is possible if average rather than worst-case appearances are bounded.

Where Pith is reading between the lines

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

  • Similar reorganization methods could be investigated for path decompositions or other width parameters.
  • These bounds might lead to improved constants in the running times of fixed-parameter tractable algorithms for problems on bounded-treewidth graphs.
  • Applications in network analysis could benefit from decompositions where high-degree nodes are not duplicated excessively.

Load-bearing premise

The method assumes that an initial tree-decomposition of width k exists for the graph and that its bags can be rearranged without violating the tree decomposition properties.

What would settle it

To disprove the claim, one would need to exhibit a graph of treewidth k whose every tree decomposition either exceeds width 14k+13 or forces some vertex v to appear in more than deg(v)+1 bags.

Figures

Figures reproduced from arXiv: 2509.01140 by David R. Wood.

Figure 1
Figure 1. Figure 1: Example of a tree division. Lemma 22. For any integer k ⩾ 2, every rooted tree T with |V (T)| ⩾ k has a division (T1, . . . , Tm) such that m ⩽ |V (T)| k−1 , and |V (Ti)| ∈ {k, . . . , 2k − 2} for each i ∈ {1, . . . , m}. Proof. We proceed by induction on |V (T)| with k fixed. If |V (T)| = k then the claim holds with T1 := T and m := 1. Now assume that |V (T)| ⩾ k + 1. By Lemma 21, there is a 9 [PITH_FULL… view at source ↗
Figure 2
Figure 2. Figure 2: Subgraphs G1 and G2, and the set S. We have shown that 4k ⩽ |Si | ⩽ 12kd for each i ∈ {1, 2}. Of course, tw(Gi) ⩽ tw(G) ⩽ k−1. Thus we may apply induction to Gi with Si the specified set. Hence Gi has a (d − 1)-slick weak tree-decomposition (Bi x : x ∈ V (Ti)) such that: • |Bi x | ⩽ 18kd for each x ∈ V (Ti)), • ∆(Ti) ⩽ 6d, • |V (Ti)| ⩽ |V (Gi)| 2k . Moreover, there is a node zi ∈ V (Ti) such that: • Si ⊆ B… view at source ↗
read the original abstract

Tree-decompositions of graphs are of fundamental importance in structural and algorithmic graph theory. The main property of tree-decompositions is the width (the maximum size of a bag minus 1). We show that every graph has a tree-decomposition with near-optimal width, where each vertex appears in few bags. In particular, every graph with treewidth $k$ has a tree-decomposition with width at most $14k+13$, where each vertex $v$ appears in at most $\text{deg}(v)+1$ bags. This improves an exponential bound by Ding and Oporowski [1995] to linear, and establishes a conjecture of theirs in a strong sense. In a second result, we show that every graph with treewidth $k$ has a tree-decomposition with width at most $3k-1$, where on average each vertex appears in at most three bags.

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

0 major / 3 minor

Summary. The paper proves that every graph of treewidth k admits a tree decomposition of width at most 14k+13 in which each vertex v appears in at most deg(v)+1 bags. It also establishes a second result: a tree decomposition of width at most 3k-1 in which vertices appear in at most three bags on average. Both results are obtained by starting from an arbitrary width-k decomposition and performing a sequence of bag reorganizations and tree modifications that preserve the three tree-decomposition axioms while controlling width, spread, order, and per-vertex multiplicity.

Significance. If the claims hold, the linear improvement over the exponential bound of Ding and Oporowski (1995) and the confirmation of their conjecture constitute a substantial advance in the structural theory of tree decompositions. The explicit, constructive nature of the reorganizations—first producing a bounded-degree/spread decomposition and then applying local replacements that increase width by a linear factor while capping appearances at deg(v)+1—provides concrete, algorithmically relevant constructions that were previously unavailable.

minor comments (3)
  1. [§2] §2 (or wherever the initial bounded-degree/spread decomposition is constructed): the transition from an arbitrary width-k decomposition to one with bounded spread and degree should include a short explicit statement of the resulting constants for spread and maximum degree, even if they are later absorbed into the 14k+13 factor.
  2. The connectedness condition for vertex subtrees is invoked repeatedly; a single sentence reminding the reader that each local replacement preserves this condition would improve readability without lengthening the argument.
  3. [Introduction] The second result (width 3k-1 with average multiplicity 3) is stated only in the abstract and introduction; a brief outline of how the averaging argument differs from the per-vertex deg(v)+1 bound would help readers compare the two theorems.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript, for the accurate summary of our results, and for the positive recommendation of minor revision. We appreciate the recognition of the improvement over the Ding-Oporowski bound and the confirmation of their conjecture.

Circularity Check

0 steps flagged

No significant circularity; constructions are independent of inputs

full rationale

The paper starts from the definitional existence of a width-k tree-decomposition and applies explicit bag-reorganization and tree-modification steps that preserve the three axioms while controlling width, spread, order, and per-vertex multiplicity. These steps are described as local replacements that increase width by a linear factor and cap appearances at deg(v)+1; they do not reduce to a fitted parameter, a self-citation chain, or a renaming of the input. The 1995 Ding-Oporowski bound is external and is improved rather than presupposed. No load-bearing premise collapses to the target result by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The claims rest on the standard definition of treewidth and tree decompositions; no free parameters, new entities, or ad-hoc axioms appear in the abstract.

axioms (1)
  • domain assumption A graph has treewidth k if it admits a tree decomposition of width k
    The statements are conditioned on graphs that already possess a decomposition of width k.

pith-pipeline@v0.9.0 · 5676 in / 1232 out tokens · 56078 ms · 2026-05-18T20:20:57.200292+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.

Forward citations

Cited by 1 Pith paper

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

  1. Tree-partitions and small-spread tree-decompositions

    math.CO 2026-04 conditional novelty 7.0

    Every graph of treewidth k and max degree Δ has a tree-partition of width O(kΔ) whose underlying tree has max degree O(Δ) and O(n/kΔ) vertices; domino treewidth is Θ(kΔ²) and a related spread-k bound is tight.

Reference graph

Works this paper leans on

67 extracted references · 67 canonical work pages · cited by 1 Pith paper · 1 internal anchor

  1. [1]

    Induced subgraphs and tree decompositions V

    Tara Abrishami, Bogdan Alecu, Maria Chudnovsky, Sepehr Hajebi, Sophie Spirkl, and Kristina Vušković. Induced subgraphs and tree decompositions V. One neighbor in a hole. J. Graph Theory, 105(4):542–561, 2024

    work page 2024

  2. [2]

    Width functions for hypertree decompositions

    Isolde Adler. Width functions for hypertree decompositions. Ph.D. thesis, Univ. Freiburg, 2006

    work page 2006

  3. [3]

    Partitioning into graphs with only small components.J

    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

  4. [4]

    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

  5. [5]

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

    work page 2008

  6. [6]

    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

  7. [7]

    Bounded-diameter tree-decompositions.Combinatorica, 44(3):659–674, 2024

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

    work page 2024

  8. [8]

    Nonserial dynamic programming

    Umberto Bertelè and Francesco Brioschi . Nonserial dynamic programming. Academic Press, 1972. 18

    work page 1972

  9. [9]

    Bodlaender

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

    work page 1988

  10. [10]

    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

  11. [11]

    Bodlaender

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

    work page 1998

  12. [12]

    Bodlaender

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

    work page 1999

  13. [13]

    Bodlaender and Joost Engelfriet

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

    work page 1997

  14. [14]

    Bodlaender, Carla Groenland, and Hugo Jacob

    Hans L. Bodlaender, Carla Groenland, and Hugo Jacob . On the parameterized complexity of computing tree-partitions. InHolger Dell and Jesper Nederlof , eds., Proc. 17th International Symposium on Parameterized and Exact Computation(IPEC 2022), vol. 249 ofLIPIcs, pp. 7:1–7:20. Schloss Dagstuhl, 2022

    work page 2022

  15. [15]

    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

  16. [16]

    A tight Erdős-Pósa function for planar minors.Adv

    Wouter Cames van Batenburg, Tony Huynh, Gwenaël Joret, and Jean-Florent Raymond. A tight Erdős-Pósa function for planar minors.Adv. Comb., #2, 2019

    work page 2019

  17. [17]

    Pascal Gollin, Kevin Hendrey, Robert Hickingbotham, Sebastian Wiederrecht, David R

    Rutger Campbell, James Davies, Marc Distel, Bryce Frederickson, J. Pascal Gollin, Kevin Hendrey, Robert Hickingbotham, Sebastian Wiederrecht, David R. Wood, and Liana Yepremyan . Treewidth, Hadwiger number, and induced minors. 2024, arXiv:2410.19295

    work page arXiv 2024

  18. [18]

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

    work page 2008

  19. [19]

    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

  20. [20]

    To approximate treewidth, use treelength! SIAM J

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

    work page 2016

  21. [21]

    The monadic second-order logic of graphs

    Bruno Courcelle. The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inform. and Comput., 85(1):12–75, 1990

    work page 1990

  22. [22]

    Fomin, Petr A

    Clément Dallard, Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen, and Martin Milanic. Computing tree decompositions with small independence number. InProc. 51st International Colloquium on Automata, Languages, and Programming(ICALP ’24, vol. 297 ofLIPIcs, pp. 51:1–51:18. Schloss Dagstuhl, 2024

    work page 2024

  23. [23]

    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

  24. [24]

    Treewidth versus clique number

    Clément Dallard, Martin Milanič, and Kenny Štorgel . Treewidth versus clique number. II. Tree-independence number.J. Combin. Theory Ser. B, 164:404–442, 2024

    work page 2024

  25. [25]

    Treewidth versus clique number

    Clément Dallard, Martin Milanič, and Kenny Štorgel . Treewidth versus clique number. III. Tree-independence number of graphs with a forbidden structure.J. Combin. Theory Ser. B, 167:338–391, 2024

    work page 2024

  26. [26]

    Treewidth versus clique number

    Clément Dallard, Matjaž Krnc, O joung Kwon, Martin Milanič, Andrea Munaro, Kenny Štorgel, and Sebastian Wiederrecht . Treewidth versus clique number. IV. Tree-independence number of graphs excluding an induced star. 2024, arXiv:2402.11222

    work page arXiv 2024

  27. [27]

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

    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

  28. [28]

    Some results on tree decomposition of graphs.J

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

    work page 1995

  29. [29]

    On tree-partitions of graphs

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

    work page 1996

  30. [30]

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

    work page arXiv 2022

  31. [31]

    Marc Distel and David R. Wood . Tree-partitions with bounded degree trees. InDavid R. Wood, Jan de Gier, and Cheryl E. Praeger , eds.,2021–2022 MATRIX Annals, pp. 203–212. Springer, 2024

    work page 2021

  32. [32]

    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

  33. [33]

    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

  34. [34]

    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

  35. [35]

    Vida Dujmović, Pat Morin, and David R. Wood . Layered separators in minor-closed graph classes with applications.J. Combin. Theory Ser. B, 127:111–147, 2017. arXiv:1306.1595

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  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]

    Treewidth of graphs with balanced separations.J

    Zdeněk Dvořák and Sergey Norin . Treewidth of graphs with balanced separations.J. Combin. Theory Ser. B, 137:137–144, 2019

    work page 2019

  38. [38]

    Zdeněk Dvořák and David R. Wood . Product structure of graph classes with strongly sublinear separators. 2022, arXiv:2208.10074

    work page arXiv 2022

  39. [39]

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

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

    work page 1986

  40. [40]

    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

  41. [41]

    Giannopoulou, O-joung Kwon, Jean-Florent Raymond, and Dim- itrios M

    Archontia C. Giannopoulou, O-joung Kwon, Jean-Florent Raymond, and Dim- itrios 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 Computer Science (WG 2016), vol. 9941 ofLecture Notes in Comput. Sci., pp. 74–84. 2016

    work page 2016

  42. [42]

    S-functions for graphs.J

    Rudolf Halin. S-functions for graphs.J. Geometry, 8(1-2):171–186, 1976

    work page 1976

  43. [43]

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

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

    work page 1991

  44. [44]

    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

  45. [45]

    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

  46. [46]

    Wood, and Liana Yepremyan

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

    work page 2021

  47. [47]

    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

  48. [48]

    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

  49. [49]

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

    work page arXiv 2024

  50. [50]

    PartitioningH-minor free graphs into three subgraphs with no large components.J

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

    work page 2018

  51. [51]

    Chun-Hung Liu and David R. Wood . Quasi-tree-partitions of graphs with an excluded subgraph. 2024, arXiv:2408.00983

    work page arXiv 2024

  52. [52]

    On the complexity of computing treelength.Discret

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

    work page 2010

  53. [53]

    Tree decompositions with bounded independence number: beyond independent sets

    Martin Milanič and Paweł Rzążewski. Tree decompositions with bounded independence number: beyond independent sets. 2022, arXiv:2209.12315. 20

    work page arXiv 2022

  54. [54]

    Three-dimensional grid drawings of graphs

    János Pach, Torsten Thiele, and Géza Tóth . Three-dimensional grid drawings of graphs. In Bernard Chazelle, Jacob E. Goodman, and Richard Pollack , eds.,Advances in discrete and computational geometry, vol. 223 ofContemporary Math., pp. 251–255. Amer. Math. Soc., 1999

    work page 1999

  55. [55]

    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

  56. [56]

    Mangoes and blueberries.Combinatorica, 19(2):267–296, 1999

    Bruce Reed. Mangoes and blueberries.Combinatorica, 19(2):267–296, 1999

    work page 1999

  57. [57]

    Bruce A. Reed . Tree width and tangles: a new connectivity measure and some applications. In R. A. Bailey , ed.,Surveys in Combinatorics, vol. 241 ofLondon Math. Soc. Lecture Note Ser., pp. 87–162. Cambridge Univ. Press, 1997

    work page 1997

  58. [58]

    Graph minors

    Neil Robertson and Paul Seymour . Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms, 7(3):309–322, 1986

    work page 1986

  59. [59]

    Graph minors

    Neil Robertson and Paul Seymour . Graph minors. V. Excluding a planar graph.J. Combin. Theory Ser. B, 41(1):92–114, 1986

    work page 1986

  60. [60]

    Graph minors

    Neil Robertson and Paul Seymour . Graph minors. X. Obstructions to tree-decomposition. J. Combin. Theory Ser. B, 52(2):153–190, 1991

    work page 1991

  61. [61]

    Tree-partite graphs and the complexity of algorithms

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

    work page 1985

  62. [62]

    Tree-chromatic number.J

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

    work page 2016

  63. [63]

    Graph searching and a min-max theorem for tree-width

    Paul Seymour and Robin Thomas . Graph searching and a min-max theorem for tree-width. J. Combin. Theory Ser. B, 58(1):22–33, 1993

    work page 1993

  64. [64]

    On the presence of disjoint subgraphs of a specified type.J

    Carsten Thomassen. On the presence of disjoint subgraphs of a specified type.J. Graph Theory, 12(1):101–111, 1988

    work page 1988

  65. [65]

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

    work page 2006

  66. [66]

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

    work page 2009

  67. [67]

    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 York J. Math., 13:117–146, 2007. 21

    work page 2007