pith. sign in

arxiv: 2507.10467 · v3 · submitted 2025-07-14 · 🧮 math.CO · cs.DM· cs.DS

Colorful Minors

Evangelos Protopapas , Dimitrios M. Thilikos , Sebastian Wiederrecht This is my paper

Pith reviewed 2026-05-19 04:43 UTC · model grok-4.3

classification 🧮 math.CO cs.DMcs.DS
keywords colorful minorsErdős-Pósa propertyfixed-parameter tractabilitygraph minorswell-quasi-orderalgorithmic meta-theoremsstructural graph theory
0
0 comments X

The pith

Colorful minors generalize rooted minors by incorporating vertex color subsets and yield a structural theory that makes testing fixed-parameter tractable.

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

The paper defines q-colorful graphs as graphs with vertices labeled by subsets of at most q colors and extends the minor relation to colorful minors by merging colors during contractions. Three theorems are proved that describe the structure of graphs avoiding colorful versions of cliques and grids, where colors are either uniform or segregated on the boundary. These insights allow a complete classification by q of colorful graphs possessing the Erdős-Pósa property for colorful minors. The structural theory also establishes that colorful minor testing is fixed-parameter tractable and that any minor-monotone parameter on colorful graphs has an FPT algorithm, along with two meta-theorems for colorful extensions of treewidth and Hadwiger number.

Core claim

We introduce the colorful minor relation on q-colorful graphs, where color sets merge at contracted edges and colors can be removed. For H being a clique with all colors, a grid with all colors, or a grid with colors segregated and ordered on the outer face, we establish three theorems characterizing the H-colorful-minor-free colorful graphs. We give a complete classification, parameterized by q, of the colorful graphs that have the Erdős-Pósa property with respect to colorful minors. Colorful minor testing is fixed-parameter tractable, and together with the well-quasi-order property this yields fixed-parameter algorithms for all colorful minor-monotone parameters. Two algorithmic meta-thems

What carries the argument

The colorful minor relation, which refines the classical minor relation by merging color sets upon contraction and permitting color deletion from vertices.

Load-bearing premise

The structural characterizations depend on limiting forbidden patterns H to fully colored cliques and grids or grids with segregated outer-face colors, and on each vertex using at most q colors.

What would settle it

Observe a q-colorful graph that has no H as colorful minor for the listed H but whose structure does not match any of the three described decompositions, for example by having large grid-like substructures with intermixed colors.

Figures

Figures reproduced from arXiv: 2507.10467 by Dimitrios M. Thilikos, Evangelos Protopapas, Sebastian Wiederrecht.

Figure 1
Figure 1. Figure 1: Two colorful graphs (G, χ) and (H, ψ) such that (H, ψ) is a colorful minor of (G, χ). The gray subgraphs of (G, χ) indicate the connected vertex sets that have to be contracted in order to form (G, ψ). Notice that it is necessary to remove some colors from some of the vertices of (G, χ). 2For n, m ∈ Z, we denote {x | 1 ≤ x ≤ n, x ∈ Z} by [n] and {x | n ≤ x ≤ m, x ∈ Z} by [n, m]. 3Notice that – in slight vi… view at source ↗
Figure 2
Figure 2. Figure 2: Three non-isomorphic (4, 3)-segregated grids. where the vertices of the first column can be numbered as v1, . . . , vqk in order of their appearance, and we have χ(u) = ∅ for all u ∈ V (G) \ {v1, . . . , vqk} and there exists a permutation π of [q] such that for every i ∈ [q], χ({vj | j ∈ [(i − 1)q + 1, iq]}) = {π(i)}. In this situation, we say that (G, χ) realizes π. See [PITH_FULL_IMAGE:figures/full_fig… view at source ↗
Figure 3
Figure 3. Figure 3: The obstructions to the Erdős-Pósa property: For [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: A schematic representation of the construction of a [PITH_FULL_IMAGE:figures/full_fig_p041_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: The 15 2-colorful graphs from the family O1 2 . The unique 2-colorful graph in O1 2 \ O˜1 2 is highlighted in the dashed square. We denote by K− 5 (resp. K− 3,3 ) the graph obtained from K5 (resp. K3,3) by deleting a single edge. For each q ∈ N≥1, we define O1 q to be the set of all the q-colorful graphs (K− 5 , ρ1), (K4, ρ2),(K− 3,3 , ρ3), and (K2,3, ρ4), where for every i ∈ [4] and each ρi , 42 [PITH_FU… view at source ↗
Figure 6
Figure 6. Figure 6: The four colorful graphs in O2 q for q = 2. For q ∈ N≥2, let O2 q be the set containing • every q-colorful graph (C4, σ1), where each vertex carries exactly one color and such that, for any two non-adjacent vertices, their palettes are disjoint from those carried by the other two. • every q-colorful graph (K3, σ2) where for each v ∈ K3, |σ(v)| = 2. • every q-colorful graph (K1,2, σ3) where for each leaf v … view at source ↗
Figure 7
Figure 7. Figure 7: A half-integral packing of size 2 of a (3, 4)-segregated grid within a (3, 8)-segregated grid of the same type. 47 [PITH_FULL_IMAGE:figures/full_fig_p050_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Left: the (1, kr)-segregated grid along with a packing of k copies of the (1, r)-segregated grid. Right: the (2, kr)-segregated grid along with a packing of k copies of the (2, r)-segregated grid. Observation 6.22. For every integer q ≥ 3 there exists a function f q 6.22 : N → N such that every connected crucial graph (H, ψ) is a colorful minor of some (2, fq 6.22(|H|))-segregated grid. The above property … view at source ↗
Figure 9
Figure 9. Figure 9: Three (2, 2)-segregated grids, each carrying the color 2, as a colorful minor of the (4, 6)-segregated grid. Observation 6.23. For every integer q ≥ 3 there exists a function f q 6.23 : N → N such that for every positive integer k, and every i ∈ [q], every (q, fq 6.23(k))-segregated grid contains q − 1 vertex-disjoint subgraphs Jj , j ∈ [q] \ {i}, such that for every j ∈ [q] \ {i} it holds that χ(V (Jj )) … view at source ↗
Figure 10
Figure 10. Figure 10: The graph Di for the case where (H, ψ) is the graph (K3, σ2) (left) or (K1,3, σ3) (right). Claim 4: (H, ψ) is neither (K3, σ2) or (K1,3, σ3). Proof of Claim 4: As before we assume the contrary. Observe that the minimality of the Di implies that – depending on the case – each Di can be constructed by considering the disjoint union of three disjoint paths P1, P2, P3, each containing two distinct vertices co… view at source ↗
Figure 11
Figure 11. Figure 11: A drawing of the slightly modified 5-multiplication of the colorful graph (G, χ) in the last part of the proof of Theorem 6.32. We just proved that if (H, ψ) is connected and has the Erdős-Pósa property, then it cannot be a member of Oq. It remains to prove that (2 · K1, τ ) does not have the Erdős-Pósa property. Let (G, χ) be a q-colorful graph that is the disjoint union of two (non-trivial) paths P1 and… view at source ↗
Figure 12
Figure 12. Figure 12: The sets U 0 6 , U 1 6 , U 2 3 , U 3 3 , and U 4 3 . 60 [PITH_FULL_IMAGE:figures/full_fig_p063_12.png] view at source ↗
read the original abstract

We introduce the notion of colorful minors, which generalizes the classical concept of rooted minors in graphs. A $q$-colorful graph is defined as a pair $(G, \chi),$ where $G$ is a graph and $\chi$ assigns to each vertex a (possibly empty) subset of at most $q$ colors. The colorful minor relation enhances the classical minor relation by merging color sets at contracted edges and allowing the removal of colors from vertices. This framework naturally models algorithmic problems involving graphs with (possibly overlapping) annotated vertex sets. We develop a structural theory for colorful minors by establishing three core theorems characterizing $\mathcal{H}$-colorful minor-free graphs, where $\mathcal{H}$ consists either of a clique or a grid with all vertices assigned all colors, or of grids with colors segregated and ordered on the outer face. Our results reveal that when exclusion is imposed not only on graphs but also to the way colors are distributed in them, a more refined structural landscape appears. Leveraging our structural insights, we provide a complete classification -- parameterized by the number $q$ of colors -- of all colorful graphs that exhibit the Erd\H{o}s-P\'osa property with respect to colorful minors. On the algorithmic side, we deduce that colorful minor testing is fixed-parameter tractable. Together with the fact that the colorful minor relation forms a well-quasi-order, this implies that every colorful minor-monotone parameter on colorful graphs admits a fixed-parameter algorithm. Furthermore, we derive two algorithmic meta-theorems (AMTs) whose structural conditions are linked to extensions of treewidth and Hadwiger number on colorful graphs. Our results suggest how known AMTs can be extended to incorporate not only the structure of the input graph but also the way the colored vertices are distributed in it.

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

2 major / 2 minor

Summary. The paper introduces colorful minors as a generalization of rooted minors on q-colorful graphs, where each vertex is assigned a subset of at most q colors. The colorful minor relation extends the standard minor relation by merging color sets upon edge contraction and permitting color removal from vertices. Three core structural theorems are proved that characterize H-colorful-minor-free graphs for H restricted to cliques or grids whose colors are either uniform across all vertices or segregated and ordered on the outer face. A complete classification, parameterized by q, is given of those colorful graphs that satisfy the Erdős-Pósa property with respect to colorful minors. Colorful-minor testing is shown to be FPT; combined with the fact that the colorful-minor relation is a well-quasi-order, this yields FPT algorithms for every colorful-minor-monotone parameter. Two algorithmic meta-theorems are derived whose structural hypotheses are expressed via colorful analogues of treewidth and Hadwiger number.

Significance. If the structural characterizations and the WQO property hold, the work supplies a refined minor theory that simultaneously tracks graph structure and the distribution of vertex annotations. The q-parameterized Erdős-Pósa classification and the derivation of FPT meta-theorems from the WQO constitute concrete strengths that could extend known algorithmic results to annotated-graph problems.

major comments (2)
  1. [Structural theorems section] The three core structural theorems (stated after the formal definition of the colorful-minor relation) characterize only the restricted families of H (cliques and grids with uniform or segregated/ordered colors). The manuscript should explicitly discuss whether the claimed decompositions extend, or fail to extend, when H is permitted to have arbitrary color assignments; otherwise the algorithmic meta-theorems rest on an unstated modeling restriction.
  2. [Well-quasi-order argument] In the proof that the colorful-minor relation is a well-quasi-order, the interaction between color merging on contractions and the standard graph-minor WQO must be verified in detail; the current argument chain appears to treat color sets as an independent quasi-order, but transitivity under simultaneous contraction and color removal is not immediate.
minor comments (2)
  1. [Abstract] The abstract announces three theorems without numbering or brief statements; adding explicit theorem references would improve readability.
  2. [Definitions] Notation for the color-assignment function χ and for the resulting colorful minor should be introduced once and used uniformly; occasional shifts between subset notation and set-union notation create minor ambiguity.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading of the manuscript and the constructive comments. We address the two major comments point by point below and will revise the manuscript to incorporate clarifications and additional details as indicated.

read point-by-point responses

  1. Referee: [Structural theorems section] The three core structural theorems (stated after the formal definition of the colorful-minor relation) characterize only the restricted families of H (cliques and grids with uniform or segregated/ordered colors). The manuscript should explicitly discuss whether the claimed decompositions extend, or fail to extend, when H is permitted to have arbitrary color assignments; otherwise the algorithmic meta-theorems rest on an unstated modeling restriction.

    Authors: We agree that the three structural theorems are formulated specifically for the restricted families of H with uniform colors (cliques and grids) or segregated and ordered colors on the outer face. These restrictions enable the decompositions we obtain. The algorithmic meta-theorems are derived directly from these characterizations. We will add an explicit discussion, most naturally placed after the statement of the theorems, clarifying that the results do not claim to cover arbitrary color assignments on H and that extending the decompositions to general colorings on H is left as an open direction. revision: yes

  2. Referee: [Well-quasi-order argument] In the proof that the colorful-minor relation is a well-quasi-order, the interaction between color merging on contractions and the standard graph-minor WQO must be verified in detail; the current argument chain appears to treat color sets as an independent quasi-order, but transitivity under simultaneous contraction and color removal is not immediate.

    Authors: The referee correctly notes that the interaction between color merging, color removal, and the underlying graph-minor operations requires careful verification for transitivity. We will expand the well-quasi-order section to include a detailed argument showing how the combined operations preserve the well-quasi-order property, explicitly addressing the composition with the standard graph-minor WQO and confirming transitivity under simultaneous contractions and color modifications. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The paper introduces the new notions of q-colorful graphs and colorful minors via explicit definitions that do not presuppose the target theorems. It then states three core structural theorems characterizing H-colorful minor-free graphs for the restricted families of H (cliques or grids with uniform or segregated colors), derives the q-parameterized Erdős-Pósa classification, and obtains FPT testing plus meta-theorems from these plus the well-quasi-order property of the colorful minor relation. No equation, prediction, or central claim reduces by construction to a fitted parameter, a self-citation chain, or a renaming of prior results; all steps rest on independent combinatorial arguments within the stated modeling choices. The derivation chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 1 invented entities

The central contribution is the definition of the colorful-minor relation and the restriction of H to cliques or grids with prescribed color distributions; no numerical free parameters appear. The work relies on standard graph-minor axioms and the well-quasi-order property of minors.

axioms (2)
  • standard math The classical minor relation is a well-quasi-order on graphs.
    Invoked to conclude that every colorful-minor-monotone parameter admits an FPT algorithm.
  • domain assumption Color sets are merged under contraction and may be removed.
    Core modeling choice stated in the definition of the colorful-minor relation.
invented entities (1)
  • colorful minor relation no independent evidence
    purpose: Generalize rooted minors to handle overlapping vertex annotations.
    Newly defined relation that merges color sets on contractions.

pith-pipeline@v0.9.0 · 5861 in / 1524 out tokens · 53317 ms · 2026-05-19T04:43:54.973605+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 2 Pith papers

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

  1. A coarse Menger's Theorem for planar and bounded genus graphs

    math.CO 2026-05 unverdicted novelty 7.0

    In planar and bounded-genus graphs, absence of k pairwise d-far S-T paths implies a vertex set of size f(d,k) whose d-neighborhood intersects every S-T path.

  2. Model Checking for Low Monodimensionality Fragments of CMSO on Topological-Minor-Free Graph Classes

    cs.LO 2026-04 unverdicted novelty 6.0

    Model checking for low-monodimensionality fragments of CMSO with disjoint-paths predicate is FPT on topological-minor-free graph classes.

Reference graph

Works this paper leans on

98 extracted references · 98 canonical work pages · cited by 2 Pith papers · 2 internal anchors

  1. [1]

    R. E. L. Aldred, S. Bau, D. A. Holton, and Brendan D. McKay. Cycles through23 vertices in 3-connected cubic planar graphs.Graphs Combin., 15(4):373–376, 1999.doi:10.1007/ s003730050046

    work page 1999

  2. [2]

    Seweryn, Stefan Weltge, and Yelena Yuditsky

    Manuel Aprile, Samuel Fiorini, Gwenaël Joret, Stefan Kober, Michał T. Seweryn, Stefan Weltge, and Yelena Yuditsky. Integer programs with nearly totally unimodular matrices: the cographic case. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2301–2312. SIAM, Philadelphia, PA, 2025.doi:10.1137/1.9781611978322. 76

    work page doi:10.1137/1.9781611978322 2025

  3. [3]

    Easy problems for tree-decomposable graphs

    Stefan Arnborg, Jens Lagergren, and Detlef Seese. Easy problems for tree-decomposable graphs. J. Algorithms, 12(2):308–340, 1991.doi:10.1016/0196-6774(91)90006-K

    work page doi:10.1016/0196-6774(91)90006-k 1991

  4. [4]

    Linear time algorithms for NP-hard problems restricted to partialk-trees

    Stefan Arnborg and Andrzej Proskurowski. Linear time algorithms for NP-hard problems restricted to partialk-trees. Discrete Appl. Math., 23(1):11–24, 1989.doi:10.1016/0166- 218X(89)90031-0

    work page doi:10.1016/0166- 1989

  5. [5]

    H. L. Bodlaender and A. M. C. A. Koster. Combinatorial Optimization on Graphs of Bounded Treewidth. The Computer Journal, 51(3):255–269, November 2007.doi:10.1093/comjnl/ bxm037

    work page doi:10.1093/comjnl/ 2007

  6. [6]

    Bodlaender, Marek Cygan, Stefan Kratsch, and Jesper Nederlof

    Hans L. Bodlaender, Marek Cygan, Stefan Kratsch, and Jesper Nederlof. Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth.Inform. and Comput., 243:86–111, 2015.doi:10.1016/j.ic.2014.12.008. 77

    work page doi:10.1016/j.ic.2014.12.008 2015

  7. [7]

    Bodlaender, Fedor V

    Hans L. Bodlaender, Fedor V. Fomin, Daniel Lokshtanov, Eelko Penninkx, Saket Saurabh, and Dimitrios M. Thilikos. (Meta) kernelization. J. ACM, 63(5):Art. 44, 69, 2016. doi: 10.1145/2973749

    work page doi:10.1145/2973749 2016

  8. [8]

    Highly linked graphs.Combinatorica, 16(3):313–320,

    Béla Bollobás and Andrew Thomason. Highly linked graphs.Combinatorica, 16(3):313–320,

    work page

  9. [9]

    doi:10.1007/BF01261316

    work page doi:10.1007/bf01261316

  10. [10]

    Borie, R

    Richard B. Borie, R. Gary Parker, and Craig A. Tovey. Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families. Algorithmica, 7(5-6):555–581, 1992.doi:10.1007/BF01758777

    work page doi:10.1007/bf01758777 1992

  11. [11]

    Erdős-Pósa property for labeled minors: 2-connected minors.SIAM J

    Henning Bruhn, Felix Joos, and Oliver Schaudt. Erdős-Pósa property for labeled minors: 2-connected minors.SIAM J. Discrete Math., 35(2):893–914, 2021.doi:10.1137/19M1289340

    work page doi:10.1137/19m1289340 2021

  12. [12]

    Improved bounds for the flat wall theorem

    Julia Chuzhoy. Improved bounds for the flat wall theorem. InProceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 256–275. SIAM, Philadelphia, PA, 2015. doi:10.1137/1.9781611973730.20

    work page doi:10.1137/1.9781611973730.20 2015

  13. [13]

    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

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

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

  14. [14]

    Automatic sequences in negative bases and proofs of some conjectures of Shevelev

    B. Courcelle. The monadic second-order logic of graphs. III. Tree-decompositions, minors and complexity issues. RAIRO Inform. Théor. Appl., 26(3):257–286, 1992.doi:10.1051/ita/ 1992260302571

    work page doi:10.1051/ita/ 1992

  15. [15]

    Courcelle

    B. Courcelle. The expression of graph properties and graph transformations in monadic second-order logic. InHandbook of graph grammars and computing by graph transformation, Vol. 1, pages 313–400. World Sci. Publ., River Edge, NJ, 1997. URL:https://doi.org/10. 1142/9789812384720_0005, doi:10.1142/9789812384720\_0005

    work page doi:10.1142/9789812384720 1997

  16. [16]

    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.doi:10.1016/0890-5401(90)90043-H

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

  17. [17]

    Counting matchings withk unmatched vertices in planar graphs

    Radu Curticapean. Counting matchings withk unmatched vertices in planar graphs. In24th Annual European Symposium on Algorithms, volume 57 ofLIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 33, 17. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2016

    work page 2016

  18. [18]

    Melin, O

    Marek Cygan, Fedor V Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh.Parameterized Algorithms. Springer Interna- tional Publishing : Imprint: Springer, Cham, 1st ed. 2015 edition, 2015.doi:10.1007/978-3- 319-21275-3

    work page doi:10.1007/978-3- 2015

  19. [19]

    Tangle-tree duality: in graphs, matroids and beyond

    Reinhard Diestel and Sang-il Oum. Tangle-tree duality: in graphs, matroids and beyond. Combinatorica, 39(4):879–910, 2019.doi:10.1007/s00493-019-3798-5

    work page doi:10.1007/s00493-019-3798-5 2019

  20. [20]

    In abstrakten Graphen vorhandene vollständige 4-Graphen und ihre Unterteilungen

    Gabriel Andrew Dirac. In abstrakten Graphen vorhandene vollständige 4-Graphen und ihre Unterteilungen. Math. Nachr., 22:61–85, 1960.doi:10.1002/mana.19600220107

    work page doi:10.1002/mana.19600220107 1960

  21. [21]

    S. E. Dreyfus and R. A. Wagner. The Steiner problem in graphs.Networks, 1:195–207, 1971/72. doi:10.1002/net.3230010302. 78

    work page doi:10.1002/net.3230010302 1971

  22. [22]

    Faudree, Ervin Györi, Yoshiyasu Ishigami, Richard H

    Yoshimi Egawa, Ralph J. Faudree, Ervin Györi, Yoshiyasu Ishigami, Richard H. Schelp, and Hong Wang. Vertex-disjoint cycles containing specified edges.Graphs Combin., 16(1):81–92,

    work page

  23. [23]

    doi:10.1007/s003730050005

    work page doi:10.1007/s003730050005

  24. [24]

    M. N. Ellingham, Michael D. Plummer, and Gexin Yu. Linkage for the diamond and the path with four vertices.J. Graph Theory, 70(3):241–261, 2012.doi:10.1002/jgt.20612

    work page doi:10.1002/jgt.20612 2012

  25. [25]

    Erickson, Clyde L

    Ranel E. Erickson, Clyde L. Monma, and Arthur F. Veinott, Jr. Send-and-split method for minimum-concave-cost network flows. Math. Oper. Res., 12(4):634–664, 1987. doi: 10.1287/moor.12.4.634

    work page doi:10.1287/moor.12.4.634 1987

  26. [26]

    Ruy Fabila-Monroy and David R. Wood. RootedK4-minors. Electron. J. Combin., 20(2):Paper 64, 19, 2013. doi:10.37236/3476

    work page doi:10.37236/3476 2013

  27. [27]

    Fellows and Michael A

    Michael R. Fellows and Michael A. Langston. Nonconstructive advances in polynomial-time complexity. Inform. Process. Lett., 26(3):157–162, 1987.doi:10.1016/0020-0190(87)90054- 8

    work page doi:10.1016/0020-0190(87)90054- 1987

  28. [28]

    Fellows and Michael A

    Michael R. Fellows and Michael A. Langston. Nonconstructive tools for proving polynomial-time decidability. J. Assoc. Comput. Mach., 35(3):727–739, 1988.doi:10.1145/44483.44491

    work page doi:10.1145/44483.44491 1988

  29. [29]

    OnH-linked graphs

    Michael Ferrara, Ronald Gould, Gerard Tansey, and Thor Whalen. OnH-linked graphs. Graphs Combin., 22(2):217–224, 2006.doi:10.1007/s00373-006-0651-6

    work page doi:10.1007/s00373-006-0651-6 2006

  30. [30]

    Face covers and rooted minors in bounded genus graphs.arXiv preprint arXiv:2503.09230, 2025

    Samuel Fiorini, Stefan Kober, Michał T Seweryn, Abhinav Shantanam, and Yelena Yuditsky. Face covers and rooted minors in bounded genus graphs.arXiv preprint arXiv:2503.09230, 2025

    work page arXiv 2025

  31. [31]

    A generalization of Dirac’s theorem on cycles throughk vertices ink-connected graphs

    Evelyne Flandrin, Hao Li, Antoni Marczyk, and Mariusz Woźniak. A generalization of Dirac’s theorem on cycles throughk vertices ink-connected graphs. Discrete Math., 307(7-8):878–884,

    work page

  32. [32]

    doi:10.1016/j.disc.2005.11.052

    work page doi:10.1016/j.disc.2005.11.052 2005

  33. [33]

    1, 2, 30

    Fedor V. Fomin, Petr A. Golovach, Ignasi Sau, Giannos Stamoulis, and Dimitrios M. Thilikos. Compound logics for modification problems.ACM Trans. Comput. Log., 26(1):2:1–2:57, 2025. doi:10.1145/3696451

    work page doi:10.1145/3696451 2025

  34. [34]

    Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi

    Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi. Hitting topological minors is FPT. InSTOC ’20—Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 1317–1326. ACM, New York, [2020] ©2020. doi:10.1145/3357713.3384318

    work page doi:10.1145/3357713.3384318 2020

  35. [35]

    Frederickson

    Greg N. Frederickson. Planar graph decomposition and all pairs shortest paths.J. Assoc. Comput. Mach., 38(1):162–204, 1991.doi:10.1145/102782.102788

    work page doi:10.1145/102782.102788 1991

  36. [36]

    M. R. Garey and D. S. Johnson. The rectilinear Steiner tree problem is NP-complete.SIAM J. Appl. Math., 32(4):826–834, 1977.doi:10.1137/0132071

    work page doi:10.1137/0132071 1977

  37. [37]

    M. R. Garey, D. S. Johnson, and L. Stockmeyer. Some simplified NP-complete graph problems. Theoret. Comput. Sci., 1(3):237–267, 1976. 79

    work page 1976

  38. [38]

    Golovach, Marcin Kamiński, Spyridon Maniatis, and Dimitrios M

    Petr A. Golovach, Marcin Kamiński, Spyridon Maniatis, and Dimitrios M. Thilikos. The parameterized complexity of graph cyclability.SIAM J. Discrete Math., 31(1):511–541, 2017. doi:10.1137/141000014

    work page doi:10.1137/141000014 2017

  39. [39]

    Golovach, Giannos Stamoulis, and Dimitrios M

    Petr A. Golovach, Giannos Stamoulis, and Dimitrios M. Thilikos. Model-checking for first-order logic with disjoint paths predicates in proper minor-closed graph classes.CoRR, abs/2211.01723,

    work page arXiv

  40. [40]

    Golovach, Giannos Stamoulis, and Dimitrios M

    URL: https://doi.org/10.48550/arXiv.2211.01723, arXiv:2211.01723, doi:10. 48550/ARXIV.2211.01723

    work page doi:10.48550/arxiv.2211.01723

  41. [41]

    Golovach, Giannos Stamoulis, and Dimitrios M

    Petr A. Golovach, Giannos Stamoulis, and Dimitrios M. Thilikos. Model-checking for first- order logic with disjoint paths predicates in proper minor-closed graph classes. In Nikhil Bansal and Viswanath Nagarajan, editors,Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, pages 3684–3699. SIA...

    work page doi:10.1137/1.9781611977554.ch141 2023

  42. [42]

    Polynomial bounds for the graph minor structure theorem.arXiv preprint arXiv:2504.02532, 2025

    Maximilian Gorsky, Michał T Seweryn, and Sebastian Wiederrecht. Polynomial bounds for the graph minor structure theorem.arXiv preprint arXiv:2504.02532, 2025

    work page arXiv 2025

  43. [43]

    Subdivision extendibility.Graphs Combin., 23(2):165–182,

    Ronald Gould and Thor Whalen. Subdivision extendibility.Graphs Combin., 23(2):165–182,

    work page

  44. [44]

    doi:10.1007/s00373-006-0665-0

    work page doi:10.1007/s00373-006-0665-0

  45. [45]

    Gould, Alexandr Kostochka, and Gexin Yu

    Ronald J. Gould, Alexandr Kostochka, and Gexin Yu. On minimum degree implying that a graph isH-linked. SIAM J. Discrete Math., 20(4):829–840, 2006.doi:10.1137/050624662

    work page doi:10.1137/050624662 2006

  46. [46]

    A polynomial time algorithm for Steiner tree when terminals avoid a rootedK4-minor

    Carla Groenland, Jesper Nederlof, and Tomohiro Koana. A polynomial time algorithm for Steiner tree when terminals avoid a rootedK4-minor. In 19th International Symposium on Parameterized and Exact Computation, volume 321 ofLIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 12, 17. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2024.doi:10.4230/ lipics.i...

    work page 2024

  47. [47]

    2011 , isbn =

    Martin Grohe, Ken-ichi Kawarabayashi, Dániel Marx, and Paul Wollan. Finding topological subgraphs is fixed-parameter tractable. In Lance Fortnow and Salil P. Vadhan, editors, Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011, pages 479–488. ACM, 2011.doi:10.1145/1993636.1993700

    work page doi:10.1145/1993636.1993700 2011

  48. [48]

    Győri and M

    E. Győri and M. D. Plummer. A nine vertex theorem for 3-connected claw-free graphs.Studia Sci. Math. Hungar., 38:233–244, 2001.doi:10.1556/SScMath.38.2001.1-4.16

    work page doi:10.1556/sscmath.38.2001.1-4.16 2001

  49. [49]

    Quickly excluding an apex- forest

    Jędrzej Hodor, Hoang La, Piotr Micek, and Clément Rambaud. Quickly excluding an apex- forest. arXiv preprint arXiv:2404.17306, 2024

    work page arXiv 2024

  50. [50]

    Bart M. P. Jansen and Céline M. F. Swennenhuis. Steiner tree parameterized by multiway cut and even less. In32nd annual European Symposium on Algorithms, volume 308 ofLIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 76, 16. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2024. doi:10.4230/lipics.esa.2024.76. 80

    work page doi:10.4230/lipics.esa.2024.76 2024

  51. [51]

    Edge multiway cut and node multiway cut are hard for planar subcubic graphs

    Matthew Johnson, Barnaby Martin, Sukanya Pandey, Daniël Paulusma, Siani Smith, and Erik Jan van Leeuwen. Edge multiway cut and node multiway cut are hard for planar subcubic graphs. In 19th Scandinavian Symposium on Algorithm Theory, volume 294 ofLIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 29, 17. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern,

    work page

  52. [52]

    doi:10.4230/lipics.swat.2024.29

    work page doi:10.4230/lipics.swat.2024.29 2024

  53. [53]

    H. A. Jung. Eine Verallgemeinerung desn-fachen Zusammenhangs für Graphen.Math. Ann., 187:95–103, 1970.doi:10.1007/BF01350174

    work page doi:10.1007/bf01350174 1970

  54. [54]

    Packing cycles through prescribed vertices

    Naonori Kakimura, Ken-ichi Kawarabayashi, and Dániel Marx. Packing cycles through prescribed vertices. J. Combin. Theory Ser. B, 101(5):378–381, 2011.doi:10.1016/j.jctb. 2011.03.004

    work page doi:10.1016/j.jctb 2011

  55. [55]

    Rooted minor problems in highly connected graphs.Discrete Math., 287(1-3):121–123, 2004.doi:10.1016/j.disc.2004.07.007

    Ken-ichi Kawarabayashi. Rooted minor problems in highly connected graphs.Discrete Math., 287(1-3):121–123, 2004.doi:10.1016/j.disc.2004.07.007

    work page doi:10.1016/j.disc.2004.07.007 2004

  56. [56]

    On sufficient degree conditions for a graph to bek-linked

    Ken-ichi Kawarabayashi, Alexandr Kostochka, and Gexin Yu. On sufficient degree conditions for a graph to bek-linked. Combin. Probab. Comput., 15(5):685–694, 2006.doi:10.1017/ S0963548305007479

    work page 2006

  57. [57]

    A new proof of the flat wall theorem

    Ken-ichi Kawarabayashi, Robin Thomas, and Paul Wollan. A new proof of the flat wall theorem. J. Combin. Theory Ser. B, 129:204–238, 2018.doi:10.1016/j.jctb.2017.09.006

    work page doi:10.1016/j.jctb.2017.09.006 2018

  58. [58]

    Quickly excluding a non-planar graph

    Ken-ichi Kawarabayashi, Robin Thomas, and Paul Wollan. Quickly excluding a non-planar graph. arXiv preprint arXiv:2010.12397, 2020

    work page arXiv 2010

  59. [59]

    A shorter proof of the graph minor algorithm—the unique linkage theorem—[extended abstract]

    Ken-ichi Kawarabayashi and Paul Wollan. A shorter proof of the graph minor algorithm—the unique linkage theorem—[extended abstract]. InSTOC’10—Proceedings of the 2010 ACM International Symposium on Theory of Computing, pages 687–694. ACM, New York, 2010

    work page 2010

  60. [60]

    NearlyETH-tightalgorithms for planar Steiner tree with terminals on few faces.ACM Trans

    SándorKisfaludi-Bak, JesperNederlof, andErikJanvanLeeuwen. NearlyETH-tightalgorithms for planar Steiner tree with terminals on few faces.ACM Trans. Algorithms, 16(3):Art. 28, 30,

    work page

  61. [61]

    Minor containment and disjoint paths in almost-linear time

    Tuukka Korhonen, Michał Pilipczuk, and Giannos Stamoulis. Minor Containment and Disjoint Paths in Almost-Linear Time. In2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pages 53–61, Chicago, IL, USA, October 2024. IEEE. doi: 10.1109/FOCS61266.2024.00014

    work page doi:10.1109/focs61266.2024.00014 2024

  62. [62]

    Minor containment and disjoint paths in almost-linear time

    Tuukka Korhonen, Michał Pilipczuk, and Giannos Stamoulis. Minor containment and disjoint paths in almost-linear time. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science—FOCS 2024, pages 53–61. IEEE Computer Soc., Los Alamitos, CA, [2024] ©2024

    work page 2024

  63. [63]

    A. V. Kostochka. The minimum Hadwiger number for graphs with a given mean degree of vertices. Metody Diskret. Analiz., (38):37–58, 1982

    work page 1982

  64. [64]

    A. V. Kostochka. Lower bound of the Hadwiger number of graphs by their average degree. Combinatorica, 4(4):307–316, 1984.doi:10.1007/BF02579141. 81

    work page doi:10.1007/bf02579141 1984

  65. [65]

    An extremal problem forH-linked graphs

    Alexandr Kostochka and Gexin Yu. An extremal problem forH-linked graphs. J. Graph Theory, 50(4):321–339, 2005.doi:10.1002/jgt.20115

    work page doi:10.1002/jgt.20115 2005

  66. [66]

    Lee, and Havana Rika

    Robert Krauthgamer, James R. Lee, and Havana Rika. Flow-cut gaps and face covers in planar graphs. InProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 525–534. SIAM, Philadelphia, PA, 2019.doi:10.1137/1.9781611975482.33

    work page doi:10.1137/1.9781611975482.33 2019

  67. [67]

    Erd\"os-P\'osa property of minor-models with prescribed vertex sets

    O-joung Kwon and Dániel Marx. Erdőos-Pósa property of minor-models with prescribed vertex sets. arXiv preprint arXiv:1904.00879, 2019

    work page internal anchor Pith review Pith/arXiv arXiv 1904

  68. [68]

    D. G. Larman and P. Mani. On the existence of certain configurations within graphs and the1- skeletons of polytopes.Proc. London Math. Soc. (3), 20:144–160, 1970.doi:10.1112/plms/s3- 20.1.144

    work page doi:10.1112/plms/s3- 1970

  69. [69]

    Asymptotic enumeration of graphs by degree sequence, and the degree sequence of a random graph.arXiv preprint arXiv:1702.08373, 2017

    Anita Liebenau and Nick Wormald. Asymptotic enumeration of graphs by degree sequence, and the degree sequence of a random graph.arXiv preprint arXiv:1702.08373, 2017

    work page arXiv 2017

  70. [70]

    Rooted grid minors.J

    Daniel Marx, Paul Seymour, and Paul Wollan. Rooted grid minors.J. Combin. Theory Ser. B, 122:428–437, 2017.doi:10.1016/j.jctb.2016.07.003

    work page doi:10.1016/j.jctb.2016.07.003 2017

  71. [71]

    Graphs on Surfaces

    Bojan Mohar and Carsten Thomassen. Graphs on Surfaces. Johns Hopkins series in the mathematical sciences. Johns Hopkins University Press, 2001. URL:https://www.press.jhu. edu/books/title/1675/graphs-surfaces

    work page 2001

  72. [72]

    Rooted Graph Minors and Reducibility of Graph Polynomials

    Benjamin Moore. Rooted graph minors and reducibility of graph polynomials.PhD Thesis, Simon Frasier University, 2017. URL: https://arxiv.org/abs/1704.04701

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  73. [73]

    Planar multiway cut with terminals on few faces,

    Sukanya Pandey and Erik Jan van Leeuwen. Planar multiway cut with terminals on few faces,

    work page

  74. [74]

    URL: https://arxiv.org/abs/2506.23399, arXiv:2506.23399

    work page arXiv

  75. [75]

    Thilikos, and Sebastian Wiederrecht

    Christophe Paul, Evangelos Protopapas, Dimitrios M. Thilikos, and Sebastian Wiederrecht. Obstructions to Erdős-Pósa dualities for minors. In2024 IEEE 65th Annual Symposium on Foundations of Computer Science—FOCS 2024, pages 31–52. IEEE Computer Soc., Los Alamitos, CA, [2024]©2024

    work page 2024

  76. [76]

    Thilikos, and Sebastian Wiederrecht

    Christophe Paul, Evangelos Protopapas, Dimitrios M. Thilikos, and Sebastian Wiederrecht. The local structure theorem for graph minors with finite index, 2025. URL:https://arxiv. org/abs/2507.02769, arXiv:2507.02769

    work page arXiv 2025

  77. [77]

    Pontecorvi and P

    M. Pontecorvi and P. Wollan. Disjoint cycles intersecting a set of vertices.J. Combin. Theory Ser. B, 102(5):1134–1141, 2012.doi:10.1016/j.jctb.2012.05.004

    work page doi:10.1016/j.jctb.2012.05.004 2012

  78. [78]

    Bruce A. Reed. Finding approximate separators and computing tree width quickly. In Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing - STOC ’92, pages 221–228, Victoria, British Columbia, Canada, 1992. ACM Press.doi:10.1145/ 129712.129734

    work page arXiv 1992

  79. [79]

    Neil Robertson and P. D. Seymour. Graph minors. XVI. Excluding a non-planar graph.J. Combin. Theory Ser. B, 89(1):43–76, 2003.doi:10.1016/S0095-8956(03)00042-X. 82

    work page doi:10.1016/s0095-8956(03)00042-x 2003

  80. [80]

    Graph Width and Well-Quasi-Ordering: A Survey

    Neil Robertson and Paul Seymour. Graph Width and Well-Quasi-Ordering: A Survey. In Progress in Graph Theory, volume 2, pages 399–406. Academic Press, Toronto, Orlando, 1984

    work page 1984

Showing first 80 references.