betaFeedback

WorksMathematics

Invitation to torso parameters of annotated graphs

Abstract

An annotated graph is a pair (G,S)(G,S), where GG is a graph and SS is a subset of vertices of GG. We present a unified approach for definitions of annotated versions of classical graph parameters such as treewidth, pathwidth, treedepth, etc. A generic way to incorporate a distinguished set of vertices into a graph parameter is via torsos. Given a graph GG and a subset S′⊆V(G)S'\subseteq V(G), we define torsoG(S′)\mathrm{torso}_G(S') to be the graph with vertex set S′S' in which distinct vertices u,v∈S′u,v\in S' are adjacent if and only if there exists a uu-vv path in GG whose internal vertices lie outside S′S'. Now let p\mathrm{p} be any graph parameter. For an annotated graph (G,S)(G,S), we define the torso p\mathrm{p} of (G,S)(G,S) by p(G,S)=min⁡{p(torsoG(S′))∣S⊂S′⊂V(G)}.\mathrm{p}(G,S) = \min\{\mathrm{p}(\mathrm{torso}_G(S')) \mid S \subset S' \subset V(G)\}. For a minor-closed class of annotated graphs C\mathcal{C}, we discuss equivalent conditions for p(G,S)\mathrm{p}(G,S) bounded for all (G,S)∈C(G,S)\in\mathcal{C} in terms of annotated graphs excluded in C\mathcal{C}. In many cases, we collect known results from the literature. We include two new arguments for p\mathrm{p} being the 22-treedepth and the feedback vertex number. Among other statements, we also include a variant of the Erdős-Pósa property for annotated cycles. We propose some new research directions.

Introduction

Structural graph theory provides a mathematical foundation for the development of powerful algorithmic techniques and the systematic design of efficient algorithms for computationally hard problems on structurally restricted graph classes. Central concepts such as graph minors and tree decompositions have played a particularly important role in this interplay between structure and algorithms. A prime example is the theory of treewidth and the celebrated Courcelle’s Theorem [6].

(Dumas, Stamoulis) Université Paris Cité, CNRS, IRIF, F-75013, Paris, France

(Hodor) Theoretical Computer Science Department, Faculty of Mathematics and Computer Science and Doctoral School of Exact and Natural Sciences, Jagiellonian University, Kraków, Poland

(Mazur, Micek) Theoretical Computer Science Department, Faculty of Mathematics and Computer Science, Jagiellonian University, Kraków, Poland

(Rambaud) Mathematics department, TU Darmstadt, Germany

E-mail addresses: [email protected], [email protected], [email protected], [email protected], [email protected], [email protected].

M. Dumas received funding from ERC grant BUKA (No. 101126229). J. Hodor is supported by a Polish Ministry of Education and Science grant (Perły Nauki; PN/01/0265/2022). T. Mazur and P. Micek were partially supported by the National Science Centre of Poland under grant UMO-2023/05/Y/ST6/00079 within the Weave-UNISONO program. C. Rambaud has been funded by the European Union through European Research Council project WYDRA, grant agreement no. 101230549. Views and opinions expressed are however those of the authors only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them. G. Stamoulis was supported by the project RBBR that is funded from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme with grant agreement No. 948057. In particular, part of work on this manuscript was done while G. Stamoulis was affiliated with University of Warsaw.

In this paper, we study classical statements from structural graph theory in a setting where a graph is equipped with a distinguished set of vertices. An annotated graph is a pair (G,S)(G,S), where GG is a graph and S⊆V(G)S \subseteq V(G). Our motivation for pursuing this line of research is twofold: algorithmic and structural.

Many problems in theoretical computer science take as input not only a graph, but also a distinguished subset of its vertices. For example, in the Sᴛᴇɪɴᴇʀ Tʀᴇᴇ problem, the input consists of a connected graph GG with nonnegative edge weights together with a subset of vertices of GG, whose elements are usually referred to as terminals. The goal is to find a connected subgraph of GG containing all terminals, possibly together with additional vertices, and having minimum total edge weight.

Although Sᴛᴇɪɴᴇʀ Tʀᴇᴇ is computationally hard in general, standard dynamic programming techniques solve it on nn-vertex graphs of treewidth at most tt in time f(t)⋅nO(1)f(t) \cdot n^{O(1)}. However, a tree decomposition of the input graph is oblivious to the distinguished set of terminals. In particular, the portion of the graph that is relevant for connecting the terminals may be structurally simple and well separated from the remainder of the graph, while the remainder itself may be arbitrarily complicated. Thus, the treewidth of the entire graph may substantially overestimate the structural complexity that is relevant to the problem.

A generic way to incorporate a distinguished set of vertices into a graph parameter is via torsos. Given a graph GG and a subset S′⊆V(G)S' \subseteq V(G), we define torso⁡G(S′)\operatorname{torso}_G(S') to be the graph with vertex set S′S' in which distinct vertices u,v∈S′u,v \in S' are adjacent if and only if there exists a uu–vv path in GG whose internal vertices lie outside S′S'. In particular, for every S′⊆V(G)S' \subseteq V(G), we have G[S′]⊆torso⁡G(S′)G[S'] \subseteq\operatorname{torso}_G(S').

Now let p be any graph parameter; formally, p is a real-valued function on the isomorphism classes of finite simple graphs. For an annotated graph (G,S)(G,S), we define the torso p of (G,S)(G,S) by

p⁡(G,S)=min⁡{p⁡(torso⁡G(S′))∣S⊆S′⊆V(G)}.\operatorname{p}(G,S)=\min\{\operatorname{p}(\operatorname{torso}_G(S')) \mid S \subseteq S' \subseteq V(G)\}.

Thus, rather than measuring the complexity of the whole graph GG, we are allowed to enlarge the distinguished set SS to a set S′S' and measure the complexity of the corresponding torso. The simplest explanation why we should consider a superset of SS comes from the following example. Consider GG to be a star with SS being the set of leaves. Then, torso⁡G(S)\operatorname{torso}_G(S) is a complete graph while GG itself is very simple.

Jansen and Swennenhuis [15] proved that the Sᴛᴇɪɴᴇʀ Tʀᴇᴇ problem can be solved efficiently on nn-vertex annotated graphs of torso treewidth at most tt in time f(t)⋅nO(1)f(t) \cdot n^{O(1)}. This provides an algorithmic indication that torso versions of classical width parameters may capture the complexity of annotated instances more accurately than the corresponding parameters of the underlying graph. The first implicit occurrence of a torso parameter that we could track is in a paper of Marx, O’Sullivan, and Razgon [19 Lemma 2.11].

We now turn to the structural motivation for studying annotated graphs. In their seminal Graph Minors series, spanning from 1983 to 2010, Robertson and Seymour developed a far-reaching theory describing the structure of graphs excluding a fixed graph as a minor. One of the central themes of this theory is the close relationship between excluded minors and width parameters such as treewidth and pathwidth. For instance, excluding a fixed planar graph as a minor is equivalent to having bounded treewidth, as follows from the Grid Minor Theorem [25]. Similarly, excluding a fixed forest as a minor is equivalent to having bounded pathwidth, as established already in the first paper of the series [24].

Recently, Hodor, La, Micek, and Rambaud [13] studied analogous statements for excluded minors of apex type. Recall, for example, that a graph is an apex-forest if it can be made acyclic by deleting at most one vertex. They proved that for every apex-forest XX, XX-minor-free graphs have bounded local pathwidth, i.e. every radius rr balls induces a subgraph of pathwidth at most O(∣V(X)∣⋅r)O(|V(X)| \cdot r). Note that a similar statement with worse bounds was proved before by Dujmović, Eppstein, Joret, Morin, and Wood [8]. A key novelty in the proof in [13] is the use of torso pathwidth.

These two independent developments, one arising from parameterized algorithms and the other from structural graph theory, suggest that width parameters for annotated graphs deserve a systematic study in their own right.

There is a very natural way of mimicking the minor relation in the realm of annotated graphs. We say that a family (Bx∣x∈V(H))(B_x \mid x \in V(H)) of pairwise disjoint subsets of vertices of GG is a model of an annotated graph (H,T)(H,T) in an annotated graph (G,S)(G,S) if

  • (i) for each x∈V(H)x \in V(H), G[Bx]G[B_x] is a connected subgraph of GG;

  • (ii) for all xy∈E(H)xy \in E(H), there exists u∈Bxu \in B_x and v∈Byv \in B_y with uv∈E(G)uv \in E(G); and

  • (iii) for each x∈Tx \in T, there exists u∈Su \in S with u∈Bxu \in B_x.

When there exists a model of an annotated graph (H,T)(H,T) in an annotated graph (G,S)(G,S), we say that (H,T)(H,T) is a minor of (G,S)(G,S). In the case where (H,V(H))(H,V(H)) is a minor of (G,S)(G,S), we also say that HH is an SS-rooted minor of GG and a model of (H,V(H))(H,V(H)) in (G,S)(G,S) is called an SS-rooted model of HH in GG. Note that HH is a minor of GG if and only if (H,V(H))(H,V(H)) is a minor of (G,V(G))(G,V(G)). Similar notions were already studied in literature [27, 17, 34].

In this paper, we study the interplay between torso parameters and excluding annotated graphs as minors. We (try to) list all the known results in this direction along with some new ones. The graph parameters that we study are: vertex cover number, treedepth, pathwidth, treewidth, 2-treedepth, feedback vertex number, and Hadwiger number; they are denoted respectively by: vc⁡(⋅)\operatorname{vc}(\cdot), td⁡(⋅)\operatorname{td}(\cdot), pw⁡(⋅)\operatorname{pw}(\cdot), tw⁡(⋅)\operatorname{tw}(\cdot), td⁡2(⋅)\operatorname{td}_2(\cdot), fv⁡(⋅)\operatorname{fv}(\cdot), and had⁡(⋅)\operatorname{had}(\cdot). For each of the parameters, we prove or cite an approximate excluded annotated minor characterization. We define

Fvc={(H,V(H))∣H is a matching},\mathcal{F}_{\mathrm{vc}} = \{(H,V(H)) \mid H \text{ is a matching}\},
Ftd={(H,V(H))∣H is a path},\mathcal{F}_{\mathrm{td}} = \{(H,V(H)) \mid H \text{ is a path}\},
Fpw={(H,V(H))∣H is a forest},\mathcal{F}_{\mathrm{pw}} = \{(H,V(H)) \mid H \text{ is a forest}\},
Ftw={(H,T)∣H is a plane graph and T is contained in the outer face of H},\mathcal{F}_{\mathrm{tw}} = \{(H,T) \mid H \text{ is a plane graph and } T \text{ is contained in the outer face of } H\},
Ftd2={(H,T)∣H is a ladder and T is a side of H},\mathcal{F}_{\mathrm{td}_2} = \{(H,T) \mid H \text{ is a ladder and } T \text{ is a side of } H\},
Ffv={(H,V(H))∣H is a disjoint union of triangles},\mathcal{F}_{\mathrm{fv}} = \{(H,V(H)) \mid H \text{ is a disjoint union of triangles}\},
Fhad={(H,V(H))∣H is a complete graph}.\mathcal{F}_{\mathrm{had}} = \{(H,V(H)) \mid H \text{ is a complete graph}\}.

A graph class is minor-closed if for every graph in the class, all its minors also belong to the class.

Theorem 1. For each p∈{vc,td,pw,tw,td2,fv,had}\mathrm{p} \in\{\mathrm{vc},\mathrm{td},\mathrm{pw},\mathrm{tw},\mathrm{td}_2,\mathrm{fv},\mathrm{had}\} and for every minor-closed class of annotated graphs C\mathcal{C}, there exists a graph (H,T)∈Fp(H,T) \in\mathcal{F}_{\mathrm{p}} with (H,T)∉C(H,T) \notin\mathcal{C} if and only if there exists a constant cc such that for every (G,S)∈C(G,S) \in\mathcal{C}, we have p(G,S)≤c\mathrm{p}(G,S) \leq c.

See a visual summary in Table 1. Theorem 1 is proved in § 3. The statements for p∈{vc,td,pw,tw}\mathrm{p} \in\{\mathrm{vc},\mathrm{td},\mathrm{pw},\mathrm{tw}\} are already known in the literature [11, 13, 4, 20], and we include them for completeness and illustration without proofs. The statement for p=had\mathrm{p}=\mathrm{had} can also be derived from known results, see [9 Corollary 13] or [21 Theorem 1.2]. Since, to our knowledge, there is no explicit proof in the literature, we include the proof. Finally, the proofs for p∈{td2,fv}\mathrm{p} \in\{\mathrm{td}_2,\mathrm{fv}\} are new. It is well-known that paths are obstructiong bounded treedepth, however, the treedepth of a path is logarithmic in its size. Kawarabayashi and Rossman [17] found obstructions for

pFp\mathcal{F}_pReference
vcred-square graph: two rows of five red squares, with vertical edges joining corresponding squaresTheorem 14
tdred-square graph: seven red squares in a horizontal path[13 Theorem 6]
pwred-square graph: two adjacent paths of three red squares joined through their upper vertices[13 Theorem 7]
twgrid graph with red-square boundary vertices and black interior vertices[20] and [13 Theorem 8]
td2_2two parallel paths, the upper with six black vertices and the lower with six red squares, joined by vertical edgesTheorem 26
fvthree triangles, each with a red square at each lower vertex and a black vertex at the topTheorem 17
hadgraph on five red-square vertices with all depicted edgesTheorem 33

Table 1. Summary of Theorem 1, which assert that, for each parameter p ∈ {vc, td, pw, tw, td2_2, fv, had}, a minor-closed class of annotated graphs has bounded p if and only if it excludes a member of Fp\mathcal{F}_p. Here, the annotated vertices are depicted as red squares.

pFp\mathcal{F}_pReference
vcred-square graph: two rows of five red squares, with vertical edges joining corresponding squaresTheorem 14
tdred-square graph: seven red squares in a horizontal path[13 Theorem 6]
pwred-square graph: two adjacent paths of three red squares joined through their upper vertices[13 Theorem 7]
twgrid graph with red-square boundary vertices and black interior vertices[20] and [13 Theorem 8]
td2_2two parallel paths, the upper with six black vertices and the lower with six red squares, joined by vertical edgesTheorem 26
fvthree triangles, each with a red square at each lower vertex and a black vertex at the topTheorem 17
hadgraph on five red-square vertices with all depicted edgesTheorem 33

bounded treedepth that have polynomial treedepth. We provide an annotated variant of this statement, see Theorem 21.

Erdős–Pósa property for annotated models

In 1965, Erdős and Pósa [10] proved that there is a function f(k)=O(klog⁡k)f(k) = O(k \log k) such that for every graph GG and every positive integer kk, either GG contains kk vertex-disjoint cycles, or there is a set XX of at most f(k)f(k) vertices of GG such that G−XG - X is a forest. Informally, we say that cycles have the Erdős–Pósa property.

Here, we are interested in Erdős–Pósa property of models of a fixed graph HH. It is well-known that models of HH have the Erdős–Pósa property if and only if HH is planar [25]. The positive direction of the statement above follows from the grid minor theorem. Van Batenburg, Huynh, Joret, and Raymond [33] proved that when HH is planar, the function witnessing the Erdős–Pósa property of models of HH is in O(klog⁡k)O(k \log k).

We are interested in the Erdős–Pósa property of models of annotated graphs in annotated graphs. The annotated variant of the grid theorem (Theorem 1 for p = tw or [13 Theorem 9]) implies that if HH is a connected planar graph with a fixed plane embedding and TT is a subset of the vertices of the outer face of HH, then the models of (H,T)(H, T) in annotated graphs have the Erdős–Pósa property.

Theorem 2 ([13 Corollary 24]). For every connected graph HH with a fixed plane embedding, for every subset T⊆V(H)T \subseteq V(H) of the vertices on the outer face of HH, there exists a function f(H,T):N→Nf_{(H,T)}: \mathbb{N} \to\mathbb{N} such that for every annotated graph (G,S)(G,S), and for every positive integer kk, either

(i) (G,S)(G,S) has kk disjoint models of (H,T)(H,T) or

(ii) there exists a set Z⊆V(G)Z \subseteq V(G) such that ∣Z∣≤f(H,T)(k)|Z| \leq f_{(H,T)}(k) and G−ZG-Z has no models of (H,T)(H,T).

Combining with the most recent improvements on the grid theorem due to Chuzhoy and Tan [3] and Bonnet [1], we may have f(H,T)(k)=O~(k33)f_{(H,T)}(k) = \widetilde{O}(k^{33}) in Theorem 2. We conjecture that f(H,T)(k)=O(klog⁡k)f_{(H,T)}(k) = O(k \log k) is possible, see Theorem 41. As evidence, we prove the first non-trivial case.

Theorem 3. Let H=K3H = K_3 and let TT be a one-vertex subset of V(H)V(H). There exists a constant cc such that for every annotated graph (G,S)(G,S) and for every positive integer kk, either

(i) (G,S)(G,S) has kk disjoint models of (H,T)(H,T) or

(ii) there exists a set Z⊆V(G)Z \subseteq V(G) such that ∣Z∣≤c⋅klog⁡k|Z| \leq c \cdot k \log k and (G−Z,S\Z)(G-Z,S\backslash Z) has no model of (H,T)(H,T).

Theorem 3 follows from Theorem 38 proved in § 4. Note that when HH is a forest, then the pathwidth part of Theorem 1, namely Theorem 12, implies that one may take f(H,T)f_{(H,T)} quadratic (see [13 Corollary 25]). Recently Claus, Joret, Rambaud, and Robinson [5] showed that in this case, f(H,T)f_{(H,T)} can be linear.

Minor-closed classes of annotated graphs

One of the fundamental results of structural graph theory due to Robertson and Seymour is that all graphs are well-quasi ordered under the minor relation. In other words, every minor-closed class of graphs has a finite list of minor-minimal obstructions. In fact, the result of Robertson and Seymour [26] is general enough so it can be also applied to annotated graphs, see also [21 Section 2.4]. Following the approach that we took for graph parameters, every minor-closed class of graphs yields a minor-closed class of annotated graphs. For every class of graphs C\mathcal{C}, let

C∙={(G,S)∣there exists S′⊆V(G) with S⊆S′ such that torso⁡G(S′)∈C}.\mathcal{C}^{\bullet} = \{(G,S) \mid\text{there exists } S' \subseteq V(G) \text{ with } S \subseteq S' \text{ such that } \operatorname{torso}_{G}(S') \in\mathcal{C}\}.

The following meta-question arises. Given a class of graphs C\mathcal{C} for which we know the minor-minimal obstructions, what are the minor-minimal obstructions of C∙\mathcal{C}^{\bullet}? We solve the first nontrivial case where C\mathcal{C} is the class of forests.

References

  1. [1]Édouard Bonnet, Codex 5.5, and Codex 5.6. An exponent 8 bound for the grid-minor theorem. Lax Archive, lax-17, 2026. laxarchive:lax-17.
  2. [2]Dario Cavallaro, Maximilian Gorsky, Stephan Kreutzer, Dimitrios M. Thilikos, and Sebastian Wiederrecht. Optimal bounds for the k-disjoint paths problem, 2026. arXiv:2605.14902.arxiv.org/abs/2605.14902
  3. [3]Julia Chuzhoy and Zihan Tan. Towards tight(er) bounds for the excluded grid theorem. Journal of Combinatorial Theory, Series B, 146:219–265, 2021. doi:10.1016/j.jctb.2020.09.010, arxiv:1901.07944.DOI
  4. [4]Quentin Claus, Jędrzej Hodor, Gwenaël Joret, and Pat Morin. Excluding an apex-forest or a fan as quickly as possible, 2026. arxiv:2602.03833.arxiv.org/abs/2602.03833
  5. [5]Quentin Claus, Gwenaël Joret, Clément Rambaud, and Eileen Robinson. Erdős-Pósa property of rooted tree minors, 2026. arXiv:2607.26638.
  6. [6]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.DOI
  7. [7]Wojciech Czerwiński, Wojciech Nadara, and Marcin Pilipczuk. Improved bounds for the excluded-minor approximation of treedepth. SIAM Journal on Discrete Mathematics, 35(2):934–947, 2021. doi:10.1137/19M128819X, arxiv:1904.13077.DOI
  8. [8]Vida Dujmović, David Eppstein, Gwenaël Joret, Pat Morin, and David R. Wood. Minor-closed graph classes with bounded layered pathwidth. SIAM Journal on Discrete Mathematics, 34(3):1693–1709, 2020. doi:10.1137/18M122162X, arxiv:1810.08314.DOI
  9. [9]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), 2025. doi:10.1007/s00493-025-00168-w, extended abstract published in the proceedings of SODA 24’ doi: 10.1137/1.9781611977912.48, arxiv:2307.02816.DOI
  10. [10]Paul Erdős and Lajos Pósa. On independent circuits contained in a graph. Canadian Journal of Mathematics, 17:347–352, 1965. doi:10.4153/CJM-1965-035-8.DOI
  11. [11]Tibor Gallai. Maximum-Minimum Sätze und verallgemeinerte Faktoren von Graphen. Acta Mathematica Hungarica, 12(1-2):131–173, 1964. doi:10.1007/BF02066678.DOI
  12. [12]Maximilian Gorsky, Evangelos Protopapas, and Sebastian Wiederrecht. Quickly Excluding an Annotated Planar Graph. In Sayan Bhattacharya, Danupon Nanongkai, Michael Benedikt, and Gabriele Puppis, editors, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026), volume 374 of Leibniz International Proceedings in Informatics (LIPIcs), pages 99:1–99:17, Dagstuhl, Germany, 2026. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2026.99.DOI
  13. [13]Jędrzej Hodor, Hoang La, Piotr Micek, and Clément Rambaud. Quickly excluding an apex-forest. SIAM Journal on Discrete Mathematics, 40(1):282–307, 2026. doi:10.1137/24M1659248, arxiv:2404.17306.DOI
  14. [14]Tony Huynh, Gwenaël Joret, Piotr Micek, Michal T. Seweryn, and Paul Wollan. Excluding a ladder. Combinatorica, 42(3):405–432, 2022. arXiv:2002.00496.DOI
  15. [15]Bart M.P. Jansen and Céline M.F. Swennenhuis. Steiner Tree Parameterized by Multiway Cut and Even Less. In 32nd Annual European Symposium on Algorithms (ESA 2024), volume 308 of Leibniz International Proceedings in Informatics (LIPIcs), pages 76:1–76:16, Dagstuhl, Germany, 2024. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ESA.2024.76, arxiv:2406.19819.DOI
  16. [16]Ken-ichi Kawarabayashi. Rooted minor problems in highly connected graphs. Discrete Mathematics, 287(1):121–123, 2004. doi:10.1016/j.disc.2004.07.007.DOI
  17. [17]Ken-ichi Kawarabayashi and Benjamin Rossman. A polynomial excluded-minor approximation of treedepth. Journal of the European Mathematical Society, 24(4):1449–1470, 2022. doi:10.4171/JEMS/1133, preliminary version published in the proceedings of SODA 18’ doi:10.1137/1.9781611795031.17.DOI
  18. [18]O-joung Kwon and Dániel Marx. Erdős-Pósa property of minor-models with prescribed vertex sets, 2019. arXiv:1904.00879.
  19. [19]Dániel Marx, Barry O’Sullivan, and Igor Razgon. Finding small separators in linear time via treewidth reduction. ACM Trans. Algorithms, 9(4), 2013. doi:10.1145/2500119, arxiv:1110.4765.DOI
  20. [20]Dániel Marx, Paul Seymour, and Paul Wollan. Rooted grid minors. Journal of Combinatorial Theory, Series B, 122:428–437, 2017. arXiv:1307.8138.
  21. [21]Evangelos Protopapas, Dimitrios M. Thilikos, and Sebastian Wiederrecht. Colorful minors, 2026. arxiv:2507.10467.arxiv.org/abs/2507.10467
  22. [22]Evangelos Protopapas, Dimitrios M. Thilikos, and Sebastian Wiederrecht. The erdős-Pósa property for colorful minors, 2026. arXiv:2609.04956.
  23. [23]Clément Rambaud. Excluding a rectangular grid, 2025. arXiv:2501.11617.arxiv.org/abs/2501.11617
  24. [24]Neil Robertson and Paul Seymour. Graph minors. I. Excluding a forest. Journal of Combinatorial Theory, Series B, 35(1):39–61, 1983. doi:10.1016/0095-8956(83)90079-5.DOI
  25. [25]Neil Robertson and Paul Seymour. Graph minors. V. Excluding a planar graph. Journal of Combinatorial Theory, Series B, 41(1):92–114, 1986. doi:10.1016/0095-8956(86)90030-4.DOI
  26. [26]Neil Robertson and Paul Seymour. Graph minors XXIII. Nash-Williams’ immersion conjecture. Journal of Combinatorial Theory, Series B, 100(2):181–205, 2010. doi:10.1016/j.jctb.2009.07.003.DOI
  27. [27]Neil Robertson and Paul Seymour. Graph minors XIII. The Disjoint Paths Problem. Journal of Combinatorial Theory, Series B, 63(1):65–110, 1995. doi:10.1006/jctb.1995.1006.DOI
  28. [28]Ignasi Sau, Nicole Schirrmacher, Sebastian Siebertz, Giannos Stamoulis, Dimitrios M. Thilikos, and Alexandre Vigny. Model Checking for Low Monodimensionality Fragments of CMSO on Topological-Minor-Free Graph Classes. In Claudia Faggian and Joost-Pieter Katoen, editors, 41st Annual Symposium on Logic in Computer Science (LICS 2026), volume 380 of Leibniz International Proceedings in Informatics (LIPIcs), pages 80:1–80:27, Dagstuhl, Germany, 2026. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.LICS.2026.80.DOI
  29. [29]Ignasi Sau, Giannos Stamoulis, and Dimitrios M. Thilikos. Parameterizing the quantification of CMSO: model checking on minor-closed graph classes, pages 3728–3742. SIAM, 2025. doi:10.1137/1.9781611978322.124, arXiv:2406.18465.DOI
  30. [30]Miklós Simonovits. A new proof and generalizations of a theorem of Erdős and Pósa on graphs without k+1 independent circuits. Acta Mathematica Academiae Scientiarum Hungaricae, 18(1–2):191–206, 1967. doi:10.1007/BF02020974.
  31. [31]Dimitrios M. Thilikos and Sebastian Wiederrecht. The graph minors structure theorem through bidimensionality, 2025. arXiv:2306.01724.arxiv.org/abs/2306.01724
  32. [32]Dimitrios M. Thilikos and Sebastian Wiederrecht. Spanning paths and cycles: Structural limitations of the irrelevant vertex technique, 2026. arXiv:2607.09342.arxiv.org/abs/2607.09342
  33. [33]Wouter Cames van Batenburg, Tony Huynh, Gwaen̈al Joret, and Jean-Florent Raymond. A tight Erdős-Pósa function for planar minors. Advances in Combinatorics, 2019. doi:10.19086/aic.10807, preliminary version published in the proceedings of SODA 19’, doi:10.1137/1.9781611975482.90, arXiv:1807.04969.DOI
  34. [34]Paul Wollan. Extremal functions for rooted minors. Journal of Graph Theory, 58(2):159–178, 2008. doi:10.1002/jgt.20301.DOI

Paper details

vlnc:W_gq7m2rdc
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents