pith. sign in

arxiv: 2304.14121 · v3 · submitted 2023-04-27 · 💻 cs.DM · math.CO

An Overview of Universal Obstructions for Graph Parameters

Christophe Paul , Evangelos Protopapas , Dimitrios M. Thilikos This is my paper

Pith reviewed 2026-05-24 09:03 UTC · model grok-4.3

classification 💻 cs.DM math.CO
keywords graph parametersobstructionsquasi-orderingsgraph minorsstructural graph theoryparameterized complexitybounded expansion
0
0 comments X

The pith

A framework of class, parametric, and universal obstructions classifies the approximate behavior of graph parameters under quasi-orderings.

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

This paper surveys how many known graph parameters fit into a parametric framework for obstruction characterizations. The framework defines three combinatorial objects that capture how a parameter behaves approximately when graphs are compared under a given quasi-ordering. The authors collect existing results from the literature and supply additional unifying classifications that place parameters into this structure. A reader would care because the approach replaces separate case-by-case analyses with a single set of obstruction concepts that predict the parameter's growth or boundedness.

Core claim

The concepts of class obstruction, parametric obstruction, and universal obstruction determine the approximate behaviour of a graph parameter with respect to a quasi-ordering on graphs. Under this framework the paper surveys existing graph-theoretic results on many known graph parameters and supplies unifying classification results.

What carries the argument

The parametric framework built from class obstructions, parametric obstructions, and universal obstructions, which together encode the approximate scaling of a graph parameter relative to a quasi-ordering.

If this is right

  • Existing obstruction theorems for individual parameters become instances of the same three-object classification.
  • Parameters not yet classified can be placed into the framework by identifying their universal obstruction.
  • The approximate behaviour of a parameter is decided once its universal obstruction is known.
  • Quasi-orderings that admit finite universal obstructions yield boundedness or linear-growth results for the parameter.

Where Pith is reading between the lines

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

  • If the framework holds, algorithmic meta-theorems that rely on obstruction sets may extend uniformly across parameters rather than being proved separately.
  • The same obstruction objects could be used to compare the structural complexity of parameters that currently lack direct comparison.
  • Testing whether a new parameter admits a finite universal obstruction becomes a concrete research task that replaces open-ended case analysis.

Load-bearing premise

The parametric framework from the authors' recent prior work applies without loss of generality to the surveyed graph parameters.

What would settle it

A concrete graph parameter for which no choice of class, parametric, or universal obstruction correctly predicts its approximate behaviour under the relevant quasi-ordering would falsify the claimed generality.

Figures

Figures reproduced from arXiv: 2304.14121 by Christophe Paul, Dimitrios M. Thilikos, Evangelos Protopapas.

Figure 1
Figure 1. Figure 1: The minor-parametric graph A = ⟨A2, A3, A4, A5, A6 . . .⟩ of annulus grids. The next proposition sums up the approximate behaviour of treewidth in terms of universal obstructions, class obstructions, and parametric obstructions. Its proof, being the first of its kind in this work, is presented in full detail. Proposition 3.1. The set {A} consisting of the minor-parametric graph A of annulus grids is a mino… view at source ↗
Figure 2
Figure 2. Figure 2: The minor-parametric graph T = ⟨T1, T2, T3, T4, . . .⟩ of complete ternary trees. Proposition 3.2. The set {T} consisting of the minor-parametric graph T of complete ternary trees is a minor-universal obstruction for pw. Moreover, cobs⩽m (pw) = {Gforest} and pobs⩽m (pw) =  {K3} [PITH_FULL_IMAGE:figures/full_fig_p014_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: The minor-parametric graph P = ⟨P1, P2, P3, P4, P5, . . .⟩ of paths. Theorem 3.3. The set {P} consisting of the minor-parametric graph P of paths is a minor-universal obstruction for td. Moreover, cobs⩽m (td) = {Glinear forest} and pobs⩽m (td) =  {K3, K1,3} [PITH_FULL_IMAGE:figures/full_fig_p015_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: The minor-parametric graph K = ⟨K2, K3, K4, K5, K6 . . .⟩ of clique grids. Let Ek denote the class of graphs embeddable in a surface of Euler genus at most k, for every non-negative integer k. Moreover, given a graph H and a set A ⊆ V (G), we say that H is an A-minor of G if there exists a collection S = {Sv | v ∈ V (H))} of pairwise vertex-disjoint connected8 subsets of V (G), each containing at least one… view at source ↗
Figure 5
Figure 5. Figure 5: The minor-parametric graph S = ⟨S2, S3, S4, S5, S6 . . .⟩ of singly-crossing grids. We define the minor-parametric graph S = ⟨Sk⟩k∈N≥2 where Sk is the singly-crossing grid depicted in [PITH_FULL_IMAGE:figures/full_fig_p018_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: The Petersen family (image taken from Wikipedia). Proposition 3.7. The set {S} consisting of the minor-parametric graph S of singly-crossing grids is a minor-universal obstruction for sc-tw. Moreover, cobs⩽m (sc-tw) = {Gsingly-crossing} and pobs⩽m (sc-tw) =  Oprojective ∪ Olinkless . 9A graph is linklessly embeddable if it has an embedding in the 3-dimensional space so that no two cycles of this embedding… view at source ↗
Figure 7
Figure 7. Figure 7: The minor-parametric graph of shallow-vortex grids V = ⟨V2, V3, V4, V5, V6 . . .⟩. We define the minor-parameteric graph V := ⟨Vt⟩t∈N≥2 of shallow-vortex grids, where for every t ≥ 2, Vt is the graph obtained from a (t × 4t)-annulus grid by adding a matching M of size 2t in its inner cycle, as illustrated in [PITH_FULL_IMAGE:figures/full_fig_p019_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: The minor-parametric graph D (1,0) = ⟨D (1,0) 2 , D (1,0) 3 , D (1,0) 4 , D (1,0) 5 , D (1,0) 6 . . .⟩ of torus grids. . . [PITH_FULL_IMAGE:figures/full_fig_p020_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: The minor-parametric graph D (0,1) = ⟨D (0,1) 2 , D (0,1) 3 , D (0,1) 4 , D (0,1) 5 , D (0,1) 6 . . .⟩ of projective grids. It can be seen [127] that D(1,0) = DΣ (1,0) captures the torus Σ (1,0), i.e., the orientable surface homeomorphic to the sphere with the addition of a handle, while D(1,0) = DΣ (0,1) captures the projective plane Σ (0,1), i.e., the non-orientable surface homeomorphic to the sphere wit… view at source ↗
Figure 10
Figure 10. Figure 10: The instance D (1,2) 8 of the minor-parametric graph D Σ(1,2) . The main result of [127] is a minor-universal obstruction for tw∗ Eg which is stated in the following proposition. Proposition 3.9. For every non-negative integer g, the set {DΣ | Σ ∈ Sg} is a minor-universal obstruction for tw∗ Eg . With respect to the vga-lattice, tw∗ Eg corresponds to a parameterization of the GMST, for each possible value… view at source ↗
Figure 11
Figure 11. Figure 11: The graphs P5, K1,4, and Ks 1,3 which are all non-isomorphic trees on four vertices. Moreover, ↓⩽m K(K2,3) is the class whose connected components are minors of K2,3. First of all, observe that K1,4 ̸ m K2,3. Therefore, obs⩽m (↓⩽m K(K2,3) ) = {G ∈ conn({6 · K1}) | K1,4 ̸ m G} ∪ {K1,4, K4, C5, Kde 3 , Kes 3 } where conn({6 · K1}) = {P6, Q2, K1,5, Ks 1,4 , Kds 1,3 , K2s 1,3} which are all non-isomorphic tre… view at source ↗
Figure 12
Figure 12. Figure 12: for an illustration of conn({6 · K1}) and [PITH_FULL_IMAGE:figures/full_fig_p025_12.png] view at source ↗
Figure 14
Figure 14. Figure 14: Two minor-parametric graphs, corresponding to the two ways triangles can be linearly arranged on a path. On the first row we have P (K3),1 = ⟨P (K3),1 2 , P (K3),1 3 , P (K3),1 4 , P (K3),1 5 , . . .⟩ while on the second row we have P (K3),2 = ⟨P (K3),2 2 , P (K3),2 3 , P (K3),2 4 , P (K3),2 5 , . . .⟩. These two minor-parametric graphs are created by the two different ways to linearly arrange triangles a… view at source ↗
Figure 15
Figure 15. Figure 15: The minor-obstruction set O (1) =  O (1) 1 , O (1) 2 , O (1) 3 [PITH_FULL_IMAGE:figures/full_fig_p029_15.png] view at source ↗
Figure 16
Figure 16. Figure 16: The minor-obstruction set O (2) =  O (2) 1 , O (2) 2 , O (2) 3 , O (2) 4 , O (2) 5 , O (2) 6 [PITH_FULL_IMAGE:figures/full_fig_p029_16.png] view at source ↗
Figure 17
Figure 17. Figure 17: The minor-parametric graph Q = ⟨Q1, Q2, Q3, Q4, Q5, . . .⟩ of ternary caterpillars. (because of K3) or minor-parametric graphs that are equivalent to the minor-parametric graph Q of ternary caterpillars (because of K1,3). Therefore, by applying Theorem 3.22, only the ternary caterpillars survive the ≲-minimization operation and we conclude with the following proposition. Theorem 3.26. The set {Q} is a min… view at source ↗
Figure 18
Figure 18. Figure 18: An instance of each of the five minor-parametric graphs obtained from the two non-isomorphic ways to linearly arrange K5 along a path and the three non-isomorphic ways to linearly arrange K3,3 along a path. and the relationship between their minor-parametric obstructions is  {P3} [PITH_FULL_IMAGE:figures/full_fig_p032_18.png] view at source ↗
Figure 19
Figure 19. Figure 19: for an illustration. . . [PITH_FULL_IMAGE:figures/full_fig_p033_19.png] view at source ↗
Figure 20
Figure 20. Figure 20: for an illustration. . . [PITH_FULL_IMAGE:figures/full_fig_p033_20.png] view at source ↗
Figure 21
Figure 21. Figure 21: The graphs K4, S3, 2 · K3, K2,3. Dang and Thomas [28] as well as Huynh, Joret, Micek, and Wood [68] independently proved that 33 [PITH_FULL_IMAGE:figures/full_fig_p033_21.png] view at source ↗
Figure 22
Figure 22. Figure 22: The minor-parametric graph L = ⟨L2, L3, L4, L5, . . .⟩ of ladders. According to [67], there exists a function f : N → N such that every graph G where btd(G) ≥ f(k) contains Lk as a minor. Moreover, it is easy to verify that btd(Lk) = Ω(log k). The graph class Gladder minors := ↓⩽m L of minors of ladders naturally arises in different contexts of graph theory. Indeed, it contains all graphs with mixed searc… view at source ↗
Figure 23
Figure 23. Figure 23: The graphs in the minor-obstruction set O L = obs⩽m (Gladder minors). 3.7.3 More on the hierarchy of minor-monotone parameters Observe that biconnected pathwidth is by definition sandwiched between treewidth and pathwidth. tw ⪯ bi-pw ⪯ pw (41) and the corresponding parametric obstructions are ordered as follows  {K3} [PITH_FULL_IMAGE:figures/full_fig_p035_23.png] view at source ↗
Figure 24
Figure 24. Figure 24: The hierarchy of minor-monotone parameters, each accompanied with some minor-universal obstruction of it. 36 [PITH_FULL_IMAGE:figures/full_fig_p036_24.png] view at source ↗
Figure 25
Figure 25. Figure 25: The immersion-parametric graph Θ = ⟨Θ1, Θ2, Θ3, Θ4, Θ5 . . .⟩ of t-pumpkins. We define the immersion-parametric graph Θ := ⟨Θt⟩t∈N, where Θt is the graph on two vertices and t parallel edges, for every t ∈ N. These graphs also known as t-pumpkins are illustrated in [PITH_FULL_IMAGE:figures/full_fig_p037_25.png] view at source ↗
Figure 26
Figure 26. Figure 26: The immersion-parametric graph W = ⟨W3, W4, W5, W6, . . .⟩ of walls. Wollan [130] proved that there exists a function f : N → N such that every graph G with tcw(G) ≥ f(k) contains Wk as an immersion, for every k ≥ 3. It is therefore implied that tcw ⪯ pW. Moreover, it is known that tw ⪯ tcw (see e.g., [130]). As already mentioned, since ∆(Wk) ≤ 3, if a graph contains Wk as an immersion, it also contains i… view at source ↗
Figure 27
Figure 27. Figure 27: The graphs K3,3, K1,4, K2 1,3, P2,2 3 , K3 1,2, Θ4. Suppose now that a graph G does not belong to P (≤3). Then, it either has a vertex of degree larger than three or it is not planar. In the first case, one of K1,4, K2 1,3 , P 2,2 3 , K3 1,2 or Θ4 is an immersion of G. In the second case G contains one of K3,3 or K5 as a topological minor. As a subcubic graph cannot contain K5 as a topological minor, we c… view at source ↗
Figure 28
Figure 28. Figure 28: The immersion-parametric graph K ds = ⟨K ds 1 , K ds 2 , K ds 3 , K ds 4 , . . .⟩ of double-edge stars. We also denote by C DS := ↓⩽iKds. Let us observe that every subdivision of K2 1,k belongs to C DS. To see this, one has to lift pairs of edges that are incident to distinct degree-two vertices. To complete the picture we need to identify the immersion obstruction set of C DS. For this, let Ods be the se… view at source ↗
Figure 29
Figure 29. Figure 29: The immersion-obstruction set O ds . Lemma 4.5. obs⩽i (C DS) = Ods . Proof. It is easy to see that for every Ods ∩ CDS = ∅ and moreover that Ods is an immersion-antichain. Let G be a graph such that Ods 1 , Ods 2 , Ods 3 , Ods 4 , Ods 5 , Ods 6 , Ods 7 , Ods 8 ⩽̸i G. Assume that there exist at least two vertices of degree at least three. Let u, v be vertices of degree at least three that are within minimu… view at source ↗
Figure 30
Figure 30. Figure 30: The immersion-parametric graph I = ⟨I1, I2, I3, I4, . . .⟩. Note that the definition of Ik has two “degrees of freedom”, contrary to the definitions of Ks and Kds . Moreover, note that every clique on k vertices is an immersion of Ik. A graph decomposition analogue of pI has been proposed by Wollan [130]. In order to describe it, we use tree-cut decompositions and we need to additionally define the notion… view at source ↗
Figure 31
Figure 31. Figure 31: The hierarchy of immersion-monotone parameters. 5 Obstructions of vertex-minor-monotone parameters In this section we turn our focus to the vertex-minor relation and discuss a few key vertex-minor￾monotone parameters and their universal obstructions. Let G be a graph and let v ∈ V (G). The result of a local complementation at a vertex v ∈ V (G) in G is the graph obtained if we remove from G all edges in G… view at source ↗
Figure 32
Figure 32. Figure 32: A graph G and a rank decomposition (T, σ) of G. The partition {σ(L e 1), σ(L e 2)} corresponding to the thick horizontal tree-edge e is {{2, 4}, {1, 5, 3}} and the corresponding matrix MG(e) has rank two. The graph G is a circle graph, as witnessed by its chord diagram on the right. The importance of rankwidth emerged from the fact that it is equivalent to the parameter cliquewidth. Here we avoid giving t… view at source ↗
Figure 33
Figure 33. Figure 33: The (3, 3)-comparability grid and its circle graph representation. Geelen, Kwon, McCarty, and Wollan showed [56] that there exists a function f : N → N so that for every k ∈ N, every graph of rankwidth at least f(k) contains as a vertex-minor the (k×k)-comparability grid G c k . In the same paper, it was observed that every circle graph is a vertex-minor of a comparability grid. As every comparability gri… view at source ↗
Figure 34
Figure 34. Figure 34: The vertex-minor obstruction set of circle graphs [13]. We conclude with the following proposition. Proposition 5.2. The set {G c} is a vertex-minor-universal obstruction for rw. Moreover, cobs⩽v (rw) =  Gcircle and pobs⩽v (rw) =  {W5, W7, W3s 3 } [PITH_FULL_IMAGE:figures/full_fig_p045_34.png] view at source ↗
Figure 35
Figure 35. Figure 35: The vertex-minor obstruction set of paths. We summarize our discussion with the following proposition. Proposition 5.3. The set {P} is a vertex-minor-universal obstruction for rkd. Moreover, cobs⩽v (rkd) =  Gpath vminors and pobs⩽v (rkd) =  {C5, K3p 3 , C2p 4 } [PITH_FULL_IMAGE:figures/full_fig_p046_35.png] view at source ↗
Figure 36
Figure 36. Figure 36: The hierarchy of vertex-minor monotone parameters. We wish to stress that our presentation of vertex-minor-monotone parameters is not exhaustive. There are more vertex-minor-monotone parameters in the literature, for which universal obstructions have been studied. For this we refer the interested reader to [82–84, 101]. 6 Obstructions of other parameters So far, we reviewed parameters that are monotone fo… view at source ↗
Figure 37
Figure 37. Figure 37: Examples of the topological minor-universal obstructions for tree-partition width. Ding and Oporowski [39] proved that there exists a function f : N → N such that every graph G where tpw(G) ≥ f(k) contains as a topological minor one of the graphs Fk, J s k , P ms k , or Wk. This means that the result of [39] can be restated as follows. 49 [PITH_FULL_IMAGE:figures/full_fig_p049_37.png] view at source ↗
Figure 38
Figure 38. Figure 38: The path P3 is a weak-topological-minor of the path P4. The double edge graph Θ2 is a weak￾topological-minor of the cycle C3. It was proved in [93] that etw is monotone under weak-topological-minors. Moreover, [93] gave a weak-topological-minor-universal obstruction for etw with respect to weak topological minors as follows. In Subsection 4.1 we defined Θ = ⟨Θk⟩k∈N, so that Θk is the graph on two vertices… view at source ↗
Figure 39
Figure 39. Figure 39: From left to right, the graphs Θ5, Θ s 5, F s 5, F ss 5 , and Ws 6. 7 Conclusion and open directions Clearly the list of parameters that we examined in this work is far from being complete. We expect that more results are known or will appear that can be stated in terms of the unified framework of universal obstructions. We conclude with some open problems and directions of research on universal obstructi… view at source ↗
read the original abstract

In a recent work, we introduced a parametric framework for obtaining obstruction characterizations of graph parameters with respect to a quasi-ordering $\leqslant$ on graphs. Towards this, we proposed the concepts of class obstruction, parametric obstruction, and universal obstruction as combinatorial objects that determine the approximate behaviour of a graph parameter. In this work, we explore its potential as a unifying framework for classifying graph parameters. Under this framework, we survey existing graph-theoretic results on many known graph parameters. Additionally, we provide some unifying results on their classification.

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 surveys existing results on graph parameters under a parametric framework (introduced in the authors' recent prior work) that uses class obstructions, parametric obstructions, and universal obstructions to characterize the approximate behavior of a parameter with respect to a quasi-ordering on graphs. It applies this framework to many known parameters and provides some unifying classification results.

Significance. If the underlying framework holds, the overview offers a systematic lens for connecting disparate obstruction results across structural graph theory, potentially aiding classification of parameters such as treewidth, chromatic number, and others. The compilation of surveyed results and the attempt at unification are explicit strengths of the manuscript.

minor comments (3)
  1. [Abstract and §1] The abstract and introduction should explicitly distinguish which definitions and theorems are restated from the prior framework paper versus newly applied or unified here, to improve self-containment for readers.
  2. [Throughout] Notation for the quasi-ordering ≤ and the obstruction concepts should be checked for consistency across sections where multiple parameters are discussed.
  3. [Survey sections] A brief table or diagram summarizing the surveyed parameters, their orderings, and the type of obstruction identified would enhance readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript, the recognition of its unifying framework and surveyed results, and the recommendation for minor revision. No specific major comments were provided in the report.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

This paper is explicitly an overview/survey applying the parametric framework (class/parametric/universal obstructions) introduced in the authors' prior work to existing results on graph parameters. The central claim that these concepts determine approximate behaviour w.r.t. a quasi-ordering originates entirely from the referenced prior work, which lies outside this document. No internal equations, predictions, or unifying results in the manuscript reduce by construction to quantities fitted or defined within this paper; the survey nature means all load-bearing content is external and independently established in the cited source.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

This is a survey paper whose claims rest on the validity of the framework defined in the authors' recent prior work and on the accuracy of the surveyed literature. No new free parameters, axioms, or invented entities are introduced in the present document.

pith-pipeline@v0.9.0 · 5609 in / 951 out tokens · 17355 ms · 2026-05-24T09:03:29.832716+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

143 extracted references · 143 canonical work pages · 3 internal anchors

  1. [1]

    Farley, and Andrzej Proskurowski

    Isolde Adler, Arthur M. Farley, and Andrzej Proskurowski. Obstructions for linear rank-width at most 1. Discret. Appl. Math., 168:3–13, 2014.doi:10.1016/j.dam.2013.05.001. 46

    work page doi:10.1016/j.dam.2013.05.001 2014

  2. [2]

    Computing excluded minors

    Isolde Adler, Martin Grohe, and Stephan Kreutzer. Computing excluded minors. InProceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 641–650. ACM, New York, 2008. URL:https://dl.acm.org/doi/10.5555/1347082.1347153. 51

    work page doi:10.5555/1347082.1347153 2008

  3. [3]

    Between clique-width and linear clique-width of bipartite graphs.Discrete Math., 343(8):111926, 14, 2020

    Bogdan Alecu, Mamadou Moustapha Kanté, Vadim Lozin, and Viktor Zamaraev. Between clique-width and linear clique-width of bipartite graphs.Discrete Math., 343(8):111926, 14, 2020. doi:10.1016/j.disc.2020.111926. 48

    work page doi:10.1016/j.disc.2020.111926 2020

  4. [4]

    Alekseev

    Vladimir E. Alekseev. On easy and hard hereditary classes of graphs with respect to the independent set problem.Discrete Applied Mathematics, 132(1):17–26, 2003. Stability in Graphs and Related Topics.doi:https://doi.org/10.1016/S0166-218X(03)00387-1. 48

    work page doi:10.1016/s0166-218x(03)00387-1 2003

  5. [5]

    A Kuratowski theorem for the projective plane.J

    Dan Archdeacon. A Kuratowski theorem for the projective plane.J. Graph Theory, 5(3):243–246,

    work page

  6. [6]

    doi:10.1002/jgt.3190050305. 18

    work page doi:10.1002/jgt.3190050305

  7. [7]

    A kuratowski theorem for nonorientable surfaces.J

    Dan Archdeacon and Phil Huneke. A kuratowski theorem for nonorientable surfaces.J. Comb. Theory, Ser. B, 46(2):173–231, 1989.doi:10.1016/0095-8956(89)90043-9. 18

    work page doi:10.1016/0095-8956(89)90043-9 1989

  8. [8]

    Atminas, R

    A. Atminas, R. Brignall, V. Lozin, and J. Stacho. Minimal classes of graphs of unbounded clique- width defined by finitely many forbidden induced subgraphs.Discrete Appl. Math., 295:57–69,

    work page

  9. [9]

    doi:10.1016/j.dam.2021.02.007. 48

    work page doi:10.1016/j.dam.2021.02.007 2021

  10. [10]

    Atminas and V

    A. Atminas and V. Lozin. A dichotomy for graphs of bounded degeneracy, 2022. URL: https://arxiv.org/abs/2206.09252, arXiv:2206.09252. 48

    work page arXiv 2022

  11. [11]

    Two short proofs concerning tree-decompositions.Com- binatorics, Probability & Computing, 11(6):541–547, 2002.doi:10.1017/S0963548302005369

    Patrick Bellenbaum and Reinhard Diestel. Two short proofs concerning tree-decompositions.Com- binatorics, Probability & Computing, 11(6):541–547, 2002.doi:10.1017/S0963548302005369. 5 52

    work page doi:10.1017/s0963548302005369 2002

  12. [12]

    Academic Press,

    Umberto Bertelé and Francesco Brioschi.Nonserial dynamic programming. Academic Press,

    work page

  13. [13]

    Seymour, and Robin Thomas

    Daniel Bienstock, Neil Robertson, Paul D. Seymour, and Robin Thomas. Quickly excluding a forest. J. Comb. Theory, Ser. B, 52(2):274–283, 1991.doi:10.1016/0095-8956(91)90068-U. 5, 6, 14

    work page doi:10.1016/0095-8956(91)90068-u 1991

  14. [14]

    Bodlaender

    Hans L. Bodlaender. A partialk-arboretum of graphs with bounded treewidth.Theor. Comput. Sci., 209(1-2):1–45, 1998.doi:10.1016/S0304-3975(97)00228-4. 12, 13

    work page doi:10.1016/s0304-3975(97)00228-4 1998

  15. [15]

    Circle graph obstructions.Journal of Combinatorial Theory Series B, 60:107–144,

    André Bouchet. Circle graph obstructions.Journal of Combinatorial Theory Series B, 60:107–144,

    work page

  16. [16]

    doi:10.1006/jctb.1994.1008. 45

    work page doi:10.1006/jctb.1994.1008 1994

  17. [17]

    Brignall and D

    R. Brignall and D. Cocks. Uncountably many minimal hereditary classes of graphs of unbounded clique-width. Electron. J. Combin., 29(1):Paper No. 1.63, 27, 2022.doi:10.37236/10483. 48

    work page doi:10.37236/10483 2022

  18. [18]

    Brignall and D

    R. Brignall and D. Cocks. A framework for minimal hereditary classes of graphs of unbounded clique-width. SIAM J. Discrete Math., 37(4):2558–2584, 2023.doi:10.1137/22M1487448. 48

    work page doi:10.1137/22m1487448 2023

  19. [19]

    Graph isomorphism parameterized by elimination distance to bounded degree

    Jannis Bulian and Anuj Dawar. Graph isomorphism parameterized by elimination distance to bounded degree. Algorithmica, 75(2):363–382, 2016.doi:10.1007/s00453-015-0045-3. 23

    work page doi:10.1007/s00453-015-0045-3 2016

  20. [20]

    Fixed-parameter tractable distances to sparse graph classes

    Jannis Bulian and Anuj Dawar. Fixed-parameter tractable distances to sparse graph classes. Algorithmica, 79(1):139–158, 2017.doi:10.1007/s00453-016-0235-7. 23, 24, 26

    work page doi:10.1007/s00453-016-0235-7 2017

  21. [21]

    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., pages Paper No. 2, 33, 2019.doi: 10.19086/aic.10807. 23, 51

    work page doi:10.19086/aic.10807 2019

  22. [22]

    Polynomial bounds for the grid-minor theorem.Journal of ACM, 63(5):40:1–40:65, 2016.doi:10.1145/2820609

    Chandra Chekuri and Julia Chuzhoy. Polynomial bounds for the grid-minor theorem.Journal of ACM, 63(5):40:1–40:65, 2016.doi:10.1145/2820609. 13

    work page doi:10.1145/2820609 2016

  23. [23]

    Fan R. K. Chung and Paul D. Seymour. Graphs with small bandwidth and cutwidth.Discret. Math., 75(1-3):113–119, 1989.doi:10.1016/0012-365X(89)90083-6. 42

    work page doi:10.1016/0012-365x(89)90083-6 1989

  24. [24]

    Towards tight(er) bounds for the excluded grid theorem.J

    Julia Chuzhoy and Zihan Tan. Towards tight(er) bounds for the excluded grid theorem.J. Comb. Theory, Ser. B, 146:219–265, 2021.doi:10.1016/j.jctb.2020.09.010. 5, 13, 41

    work page doi:10.1016/j.jctb.2020.09.010 2021

  25. [25]

    Collins, J

    A. Collins, J. Foniok, N. Korpelainen, V. Lozin, and V. Zamaraev. Infinitely many minimal classes of graphs of unbounded clique-width.Discrete Appl. Math., 248:145–152, 2018.doi: 10.1016/j.dam.2017.02.012. 48

    work page doi:10.1016/j.dam.2017.02.012 2018

  26. [26]

    The monadic second-order logic of graphs

    Bruno Courcelle. The monadic second-order logic of graphs. I. recognizable sets of finite graphs. Information and Computation, 85(1):12–75, 1990.doi:10.1016/0890-5401(90)90043-H. 4, 13

    work page doi:10.1016/0890-5401(90)90043-h 1990

  27. [27]

    The monadic second-order logic of graphs III: tree-decompositions, minor and complexity issues.RAIRO - Theoretical Informatics and Applications, 26:257–286, 1992

    Bruno Courcelle. The monadic second-order logic of graphs III: tree-decompositions, minor and complexity issues.RAIRO - Theoretical Informatics and Applications, 26:257–286, 1992. doi:10.1051/ita/1992260302571. 4, 13

    work page doi:10.1051/ita/1992260302571 1992

  28. [28]

    The expression of graph properties and graph transformations in monadic second-order logic

    Bruno Courcelle. The expression of graph properties and graph transformations in monadic second-order logic. InHandbook of Graph Grammars and Computing by Graph Transformations, Volume 1: Foundations, pages 313–400. World Scientific, 1997. 4, 13

    work page 1997

  29. [29]

    Handle-rewriting hypergraph grammars

    Bruno Courcelle, Joost Engelfriet, and Grzegorz Rozenberg. Handle-rewriting hypergraph grammars. J. Comput. Syst. Sci., 46(2):218–270, 1993.doi:10.1016/0022-0000(93)90004-G. 44 53

    work page doi:10.1016/0022-0000(93)90004-g 1993

  30. [30]

    Makowsky, and Udi Rotics

    Bruno Courcelle, Johann A. Makowsky, and Udi Rotics. Linear time solvable optimization problems on graphs of bounded clique-width.Theory of Computing Systems, 33(2):125–150,

    work page

  31. [31]

    doi:10.1007/s002249910009. 5, 44

    work page doi:10.1007/s002249910009

  32. [32]

    Minors of two-connected graphs of large path-width

    Thanh N. Dang and Robin Thomas. Minors of two-connected graphs of large path-width, 2018. arXiv:1712.04549. 33, 34

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  33. [33]

    David Dekker and Bart M. P. Jansen. Kernelization for feedback vertex set via elimination distance to a forest. In Michael A. Bekos and Michael Kaufmann, editors,Graph-Theoretic Concepts in Computer Science - 48th International Workshop, WG 2022, Tübingen, Germany, June 22-24, 2022, Revised Selected Papers, volume 13453 ofLecture Notes in Computer Science...

    work page doi:10.1007/978-3-031-15914-5 2022

  34. [34]

    Demaine, Mohammad Taghi Hajiaghayi, Naomi Nishimura, Prabhakar Ragde, and Dimitrios M

    Erik D. Demaine, Mohammad Taghi Hajiaghayi, Naomi Nishimura, Prabhakar Ragde, and Dimitrios M. Thilikos. Approximation algorithms for classes of graphs excluding single-crossing graphs as minors.J. Comput. Syst. Sci., 69(2):166–195, 2004.doi:10.1016/j.jcss.2003.12

    work page doi:10.1016/j.jcss.2003.12 2004

  35. [35]

    Demaine, Mohammad Taghi Hajiaghayi, and Dimitrios M

    Erik D. Demaine, Mohammad Taghi Hajiaghayi, and Dimitrios M. Thilikos. Exponential speedup of fixed-parameter algorithms for classes of graphs excluding single-crossing graphs as minors. Algorithmica, 41(4):245–267, 2005.doi:10.1007/s00453-004-1125-y. 18

    work page doi:10.1007/s00453-004-1125-y 2005

  36. [36]

    Demaine, MohammadTaghi Hajiaghayi, and Ken-ichi Kawarabayashi

    Erik D. Demaine, MohammadTaghi Hajiaghayi, and Ken-ichi Kawarabayashi. Algorithmic graph minor theory: Improved grid minor bounds and wagner’s contraction.Algorithmica, 54(2):142–180, 2009.doi:10.1007/s00453-007-9138-y. 13

    work page doi:10.1007/s00453-007-9138-y 2009

  37. [37]

    Branch-depth: generalizing tree-depth of graphs

    Matt DeVos, O-joung Kwon, and Sang-il Oum. Branch-depth: generalizing tree-depth of graphs. European Journal of Combinatorics, 90:103186, 2020. doi:10.1016/j.ejc.2020.103186. 46

    work page doi:10.1016/j.ejc.2020.103186 2020

  38. [38]

    Graph Theory, volume 173

    Reinhard Diestel. Graph Theory, volume 173. Springer-Verlag, 5th edition, 2017.doi:10.1007/ 978-3-662-53622-3. 5

    work page 2017

  39. [39]

    Giannopoulou, Giannos Stamoulis, and Dimitrios M

    Öznur Yasar Diner, Archontia C. Giannopoulou, Giannos Stamoulis, and Dimitrios M. Thilikos. Block elimination distance.Graphs Comb., 38(5):133, 2022.doi:10.1007/s00373-022-02513-y. 23, 34

    work page doi:10.1007/s00373-022-02513-y 2022

  40. [40]

    Excluding a long double path minor.J

    Guoli Ding. Excluding a long double path minor.J. Combin. Theory Ser. B, 66(1):11–23, 1996. doi:10.1006/jctb.1996.0002. 49

    work page doi:10.1006/jctb.1996.0002 1996

  41. [41]

    Excluded-minor characterization of apex-outerplanar graphs

    Guoli Ding and Stan Dziobiak. Excluded-minor characterization of apex-outerplanar graphs. Graphs Comb., 32(2):583–627, 2016.doi:10.1007/s00373-015-1611-9. 24

    work page doi:10.1007/s00373-015-1611-9 2016

  42. [42]

    Some results on tree decomposition of graphs.Journal of Graph Theory, 20(4):481–499, 1995.doi:10.1002/jgt.3190200412

    Guoli Ding and Bogdan Oporowski. Some results on tree decomposition of graphs.Journal of Graph Theory, 20(4):481–499, 1995.doi:10.1002/jgt.3190200412. 49

    work page doi:10.1002/jgt.3190200412 1995

  43. [43]

    On tree-partitions of graphs

    Guoli Ding and Bogdan Oporowski. On tree-partitions of graphs. Discrete Mathematics, 149(1-3):45–58, 1996.doi:10.1016/0012-365X(94)00337-I. 49

    work page doi:10.1016/0012-365x(94)00337-i 1996

  44. [44]

    Michael J. Dinneen. Too many minor order obstructions (for parameterized lower ideals).Journal of Universal Computer Science, 3(11):1199–1206, 1997.doi:10.3217/jucs-003-11. 26

    work page doi:10.3217/jucs-003-11 1997

  45. [45]

    Dinneen, Kevin Cattell, and Michael R

    Michael J. Dinneen, Kevin Cattell, and Michael R. Fellows. Forbidden minors to graphs with small feedback sets.Discret. Math., 230(1-3):215–252, 2001.doi:10.1016/S0012-365X(00)00083-2. 33 54

    work page doi:10.1016/s0012-365x(00)00083-2 2001

  46. [46]

    Semi-nice tree-decompositions: The best of branchwidth, treewidth and pathwidth with one algorithm.Discrete Applied Mathematics, 157(12):2737–2746,

    Frederic Dorn and Jan Arne Telle. Semi-nice tree-decompositions: The best of branchwidth, treewidth and pathwidth with one algorithm.Discrete Applied Mathematics, 157(12):2737–2746,

    work page

  47. [47]

    doi:10.1016/j.dam.2008.08.023. 5

    work page doi:10.1016/j.dam.2008.08.023 2008

  48. [48]

    Downey and Michael R

    Rod G. Downey and Michael R. Fellows.Parameterized complexity. Springer, 1999. 4

    work page 1999

  49. [49]

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

    work page doi:10.1137/s0097539702416141 2005

  50. [50]

    Beiträge zur Analysis situs.Math

    Walther Dyck. Beiträge zur Analysis situs.Math. Ann., 32(4):457–512, 1888.doi:10.1007/ BF01443580. 20

    work page

  51. [51]

    A Unifying Framework for Characterizing and Computing Width Measures

    Eduard Eiben, Robert Ganian, Thekla Hamm, Lars Jaffke, and O-joung Kwon. A Unifying Framework for Characterizing and Computing Width Measures. InInnovations in Theoretical Computer Science Conference (ITCS), volume 215 of Leibniz International Proceedings in Informatics (LIPIcs), pages 63:1–63:23, 2022.doi:10.4230/LIPIcs.ITCS.2022.63. 4

    work page doi:10.4230/lipics.itcs.2022.63 2022

  52. [52]

    P. Erdős. Graph theory and probability.Canadian J. Math., 11:34–38, 1959.doi:10.4153/ CJM-1959-003-9. 48

    work page 1959

  53. [53]

    Fellows and Micheal A

    Michael R. Fellows and Micheal A. Langston. On well-partial-order theory and its application to combinatoria problems of VLSI design.SIAM Journal on Discrete Mathematics, 5(1):117–126,

    work page

  54. [54]

    doi:10.1137/0405010. 11

    work page doi:10.1137/0405010

  55. [55]

    American Mathematical Society, Providence, RI, 2017.doi:10.1090/conm/689

    Erica Flapan, Allison Henrich, Aaron Kaestner, and Sam Nelson.Knots, links, spatial graphs, and algebraic invariants, volume 689 ofContemporary Mathematics. American Mathematical Society, Providence, RI, 2017.doi:10.1090/conm/689. 26

    work page doi:10.1090/conm/689 2017

  56. [56]

    Francis and Jeffrey R

    George K. Francis and Jeffrey R. Weeks. Conway’s ZIP proof.Amer. Math. Monthly, 106(5):393– 399, 1999. doi:10.2307/2589143. 20

    work page doi:10.2307/2589143 1999

  57. [57]

    Are there any good digraph width measures?J

    Robert Ganian, Petr Hliněný, Joachim Kneis, Daniel Meister, Jan Obdržálek, Peter Rossmanith, and Somnath Sikdar. Are there any good digraph width measures?J. Combin. Theory Ser. B, 116:250–286, 2016.doi:10.1016/j.jctb.2015.09.001. 4

    work page doi:10.1016/j.jctb.2015.09.001 2016

  58. [58]

    Slim tree-cut width

    Robert Ganian and Viktoriia Korchemna. Slim tree-cut width. In Holger Dell and Jesper Nederlof, editors, 17th International Symposium on Parameterized and Exact Computation, IPEC 2022, September 7-9, 2022, Potsdam, Germany, volume 249 ofLIPIcs, pages 15:1–15:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.doi:10.4230/LIPIcs.IPEC.2022.15. 39, 40, 41

    work page doi:10.4230/lipics.ipec.2022.15 2022

  59. [59]

    Garey and David S

    Micheal R. Garey and David S. Johnson.Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, 1979. 11

    work page 1979

  60. [60]

    Tangles, tree-decompositions and grids in matroids

    Jim Geelen, Bert Gerards, and Geoff Whittle. Tangles, tree-decompositions and grids in matroids. Journal of Combinatorial Theory, Series B, 99(4):657–667, 2009.doi:10.1016/j.jctb.2007. 10.008. 52

    work page doi:10.1016/j.jctb.2007 2009

  61. [61]

    A generalization of the Grid Theorem

    Jim Geelen and Benson Joeris. A generalization of the grid theorem, 2016.arXiv:1609.09098. 13, 14

    work page internal anchor Pith review Pith/arXiv arXiv 2016

  62. [62]

    The grid theorem for vertex-minors

    Jim Geelen, O-joung Kwon, Rose McCarty, and Paul Wollan. The grid theorem for vertex-minors. J. Combin. Theory Ser. B, 158:93–116, 2023.doi:10.1016/j.jctb.2020.08.004. 6, 45

    work page doi:10.1016/j.jctb.2020.08.004 2023

  63. [63]

    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-expansions of planar sub-cubic graphs.European Journal of Combinatorics, 65:154–167, 2017.doi:10.1016/j.ejc.2017.05.009. 49 55

    work page doi:10.1016/j.ejc.2017.05.009 2017

  64. [64]

    103 graphs that are irreducible for the projective plane.Journal of Combinatorial Theory, Series B, 27(3):332–370, 1979

    Henry H Glover, John P Huneke, and Chin San Wang. 103 graphs that are irreducible for the projective plane.Journal of Combinatorial Theory, Series B, 27(3):332–370, 1979. URL: https://www.sciencedirect.com/science/article/pii/0095895679900224, doi:https:// doi.org/10.1016/0095-8956(79)90022-4. 18

    work page doi:10.1016/0095-8956(79)90022-4 1979

  65. [65]

    Finding topological subgraphs is fixed-parameter tractable

    Martin Grohe, Ken-ichi Kawarabayashi, Dániel Marx, and Paul Wollan. Finding topological subgraphs is fixed-parameter tractable. InAnnual ACM on Symposium on Theory of Computing (STOC), pages 479–488, 2011.doi:10.1145/1993636.1993700. 4

    work page doi:10.1145/1993636.1993700 2011

  66. [66]

    Improved bounds on the planar branchwidth with respect to the largest grid minor size.Algorithmica, 64(3):416–453, 2012.doi:10.1007/s00453-012-9627-5

    Qian-Ping Gu and Hisao Tamaki. Improved bounds on the planar branchwidth with respect to the largest grid minor size.Algorithmica, 64(3):416–453, 2012.doi:10.1007/s00453-012-9627-5. 5

    work page doi:10.1007/s00453-012-9627-5 2012

  67. [67]

    über eine Klassifikation der Streckenkomplex.Vierteljschr

    Hugo Hadwiger. über eine Klassifikation der Streckenkomplex.Vierteljschr. Naturforsch. Ges. Zürich, 88:133–143, 1943. 16

    work page 1943

  68. [68]

    Tree-partitions of infinite graphs.Discrete Mathematics, 97(1-3):203–217, 1991

    Rudolf Halin. Tree-partitions of infinite graphs.Discrete Mathematics, 97(1-3):203–217, 1991. 49

    work page 1991

  69. [69]

    Harvey and David R

    Daniel J. Harvey and David R. Wood. Parameters tied to treewidth.J. Graph Theory, 84(4):364– 385, 2017. doi:10.1002/jgt.22030. 5, 34

    work page doi:10.1002/jgt.22030 2017

  70. [70]

    Cyclewidth and the Grid Theorem for Perfect Matching Width of Bipartite Graphs

    Meike Hatzel, Roman Rabinovich, and Sebastian Wiederrecht. Cyclewidth and the grid theorem for perfect matching width of bipartite graphs.CoRR, abs/1902.01322, 2019. URL:arxiv.org/ abs/1902.01322, arXiv:1902.01322. 52

    work page internal anchor Pith review Pith/arXiv arXiv 1902

  71. [71]

    Finding branch-decompositions and rank-decompositions.SIAM Journal on Computing, 38(3):1012–1032, 2008.doi:10.1137/070685920

    Petr Hliněný and Sang-il Oum. Finding branch-decompositions and rank-decompositions.SIAM Journal on Computing, 38(3):1012–1032, 2008.doi:10.1137/070685920. 5

    work page doi:10.1137/070685920 2008

  72. [72]

    Width parameters beyond tree-width and their applications

    Petr Hliněný, Sang-il Oum, Detlef Seese, and Georg Gottlob. Width parameters beyond tree-width and their applications. The Computer Journal, 51(3):326–362, 09 2007.arXiv: https://academic.oup.com/comjnl/article-pdf/51/3/326/1139343/bxm052.pdf, doi:10. 1093/comjnl/bxm052. 4

    work page 2007

  73. [73]

    Seweryn, and Paul Wollan

    Tony Huynh, Gwenaël Joret, Piotr Micek, Michał T. Seweryn, and Paul Wollan. Excluding a ladder. Combinatorica, 42(3):405–432, 2022.doi:10.1007/s00493-021-4592-8. 34

    work page doi:10.1007/s00493-021-4592-8 2022

  74. [74]

    Tony Huynh, Gwenaël Joret, Piotr Micek, and David R. Wood. Seymour’s conjecture on 2-connected graphs of large pathwidth. Combinatorica, 40:839–868, 2020. doi:10.1007/ s00493-020-3941-3. 6, 33, 34

    work page 2020

  75. [75]

    A polynomial excluded-minor approximation of tree-depth

    Ken ichi Kawarabayashi and Benjamin Rossman. A polynomial excluded-minor approximation of tree-depth. InAnnual ACM-SIAM Symposium on Discrete Mathematics, pages 234–246, 2018. doi:10.1137/1.9781611975031.17. 15

    work page doi:10.1137/1.9781611975031.17 2018

  76. [76]

    A note on well quasi-orderings for powersets.Inf

    Petr Jancar. A note on well quasi-orderings for powersets.Inf. Process. Lett., 72(5-6):155–160,

    work page

  77. [77]

    doi:10.1016/S0020-0190(99)00149-0. 9

    work page doi:10.1016/s0020-0190(99)00149-0

  78. [78]

    Jobson and André E

    Adam S. Jobson and André E. Kézdy. All minor-minimal apex obstructions with connectivity two. Electronic Journal of Combinatorics, 28(1):1.23, 58, 2021.doi:10.37236/8382. 26

    work page doi:10.37236/8382 2021

  79. [79]

    MAX-CUT and containment relations in graphs.Theoret

    Marcin Kamiński. MAX-CUT and containment relations in graphs.Theoret. Comput. Sci., 438:89–95, 2012.doi:10.1016/j.tcs.2012.02.036. 17

    work page doi:10.1016/j.tcs.2012.02.036 2012

  80. [80]

    Linear rank-width of distance-hereditary graphs II

    Mamadou Moustapha Kanté and O-joung Kwon. Linear rank-width of distance-hereditary graphs II. vertex-minor obstructions.European Journal of Combinatorics, 74:110–139, 2018. doi:10.1016/j.ejc.2018.07.009. 6, 46 56

    work page doi:10.1016/j.ejc.2018.07.009 2018

Showing first 80 references.