Colorful Minors

Our core contributions are a series of structural theorems for $(H,\psi )$-colorful minor-free $q$-colorful graphs, both for general $(H,\psi )$ and for the particular case where $H$ is planar – under two distinct assumptions on the distribution of colors. Our results use as a departure point the notion of the bidimensionality of a vertex set and related structural concepts [41, 42, 43]. Building on our structural theorems, we derive a complete classification of all $q$-colorful graphs that satisfy the Erdős-Pósa property, for every $q\in \mathbb{N}$ (under the colorful minor relation).

Our next step is to apply our structural theorems to algorithmic settings, with the broader goal of developing an algorithmic graph structure theory applicable to problems involving vertex annotations. To this end, we first observe that colorful graphs are well quasi-ordered under the colorful minor relation. We also provide an algorithm that decides whether a $q$-colorful graph $(H,\psi )$ is a colorful minor of a $q$-colorful graph $(G,\chi )$ in time³³3By $g(n)\in {𝒪}_k(f(n))$ we mean that there is a function $h:\mathbb{N}\to \mathbb{N}$ such that $g(n)\in 𝒪(h(k)\cdot f(n)).$ Also, given a graph $G,$ we use $|G|$ and $\Vert G\Vert$ for the number of its vertices and edges respectively. ${𝒪}_{|H|+q}({\Vert G\Vert }^{1+o(1)}).$ These two facts imply that membership for any colorful minor-closed class of colorful graphs is decidable in polynomial time.

Next, we show how classical algorithmic meta-theorems (AMTs) – such as Courcelle’s Theorem and the recent algorithmic meta-theorem of Sau, Stamoulis, and Thilikos [54] – can be extended to colorful graphs, where the structural conditions are expressed via the exclusion of colorful minors. This framework enables the resolution of problems on graphs containing arbitrarily large grid or clique minors while, up to now, the exclusion of a minor appeared as a necessary (sparsity) condition. Our results support a key insight emerging from the body of work mentioned above:

Problem complexity does not only depend on the global structure of the input graph,
but crucially on how t he annotated sets are distributed within it.

The algorithmic results presented here are not intended to be exhaustive; rather, they serve to illustrate this principle and to lay the groundwork for future exploration of algorithmic problems involving vertex annotations. In particular, we provide algorithmic applications for two of our three main structural results – Theorems 2 and 3 – while leaving the investigation of algorithmic consequences of Theorem 4 to future work.

Let $q$ be a non-negative integer. A $q$-colorful graph is a pair $(G,\chi )$ where $G$ is a graph and⁴⁴4For $n,m\in \mathbb{Z},$ we denote $\{x\mid 1\le x\le n\text{, }x\in \mathbb{Z}\}$ by $[n]$ and $\{x\mid n\le x\le m\text{, }x\in \mathbb{Z}\}$ by $[n,m].$ $\chi :V(G)\to 2^{[q]}.$ For a vertex $v\in V(G)$ we call $\chi (v)$ the palette of $v.$ For illustrations, we use magenta for $1,$ blue for $2$, yellow for $3,$ and green for $4.$

Certainly, every vertex of $G$ receives a (possibly empty) subset of colors. Given a vertex set $X\subseteq V(G),$ we define $\chi (X)≔{\bigcup }_{v\in X}\chi (v)$. We also use notation $\chi (G)≔\chi (V(G))$. Similarly, for $I\subseteq [q]$ we denote by ${\chi }^{-1}(I)$ the set $\{v\in V(G):I\cap \chi (v)\ne \mathrm{\varnothing }\}.$ When $I=\{i\}$ is a singleton, we write ${\chi }^{-1}(i)$ instead of ${\chi }^{-1}(\{i\}).$

A $q$-colorful graph $(G,\chi )$ where $\chi (G)⊊[q]$ is called restricted and a $q$-colorful graph $(G,\chi )$ with $\chi (G)=\mathrm{\varnothing }$ is called empty. Note that any restricted $q$-colorful graph is also a $(q-1)$-colorful graph, so the notion of being restricted is highly dependent on the context given by the total set of colors. Finally, a $q$-colorful graph $(G,\chi )$ is said to be rainbow⁵⁵5Notice that – in slight violation of the English language – we use the word “rainbow” as an adjective here. if $\chi (v)=[q]$ for all $v\in V(G).$

A colorful graph $(H,\psi )$ is a (colorful) subgraph of a colorful graph $(G,\chi ),$ denoted by $(H,\psi )\subseteq (G,\chi ),$ if $H$ is a subgraph of $G$ and $\psi (v)\subseteq \chi (v)$ for all $v\in V(H).$ If $(G,\chi )$ is a colorful graph and $H\subseteq G$ is a subgraph of $G$ we write, in slight abuse of notation, $(H,\chi )$ for the $q$-colorful subgraph of $(G,\chi )$ where all vertices of $H$ receive precisely the colors they received in $(G,\chi ).$

A colorful graph $(H,\psi )$ is a colorful minor of a colorful graph $(G,\chi )$ if $(H,\psi )$ can be obtained from $(G,\psi )$ by means of the following operations:

• $\mathrm{■}$

  deleting an edge $e\in E(G),$

• $\mathrm{■}$

  deleting a vertex $v\in V(G)$ and restricting the domain of $\chi$ to $V(G)\setminus \{v\},$

• $\mathrm{■}$

  for some $v\in V(G)$ and $i\in \chi (v)$ overwrite $\chi (v)≔\chi (v)\setminus \{i\}$ (we refer to this operation as removing a color (from $v$)), and

• $\mathrm{■}$

  contracting an edge $uv\in E(G),$ that is introducing a new vertex $x_{uv}$ with neighborhood $N_G(u)\cup N_G(v),$ setting $\chi (x_{uv})≔\chi (u)\cup \chi (v),$ and then deleting both $u$ and $v$ from the resulting colorful graph.

See Figure 1 for an example. Notice that $1$-colorful graphs are exactly annotated graphs and the notions of colorful minors and rooted minors coincide on annotated graphs.

We derive the following, as a simple consequence of a deep theorem of Robertson and Seymour [53].

We prove a total of three structure theorems as follows. The first two describe the structure of graphs excluding the $q$-colorful rainbow $t$-clique and the $q$-colorful rainbow $(k\times k)$-grid respectively as a colorful minor. Moreover, we generalize a theorem of Marx, Seymour, and Wollan [37], that describes the structure of $1$-colorful graphs excluding a $(k\times k)$-grid where exactly the vertices of the first row receive color $1,$ to an arbitrary number of colors.

We begin with our simplest result – excluding a rainbow clique – which can be naturally phrased in terms of a modulator to restricted graphs. For a vertex set $X\subseteq V(G)$ in a graph $G$ we define the torso of $X$ in $G,$ denoted by $\mathrm{𝗍𝗈𝗋𝗌𝗈}(G,X),$ as the graph obtained from $G[X]$ by turning the neighborhood of $J$ in $X$ into a clique for every component $J$ of $G-X.$ In short, every $q$-colorful graph $(G,\chi )$ that excludes a rainbow clique as a colorful minor has a set $X$ whose torso excludes a minor and where every component of $(G-X,\chi )$ is free of some (not necessarily the same) color.

A tree-decomposition for a graph $G$ is a pair $𝒯=(T,\beta )$ where $T$ is a tree and $\beta :V(T)\to 2^{V(G)},$ called the bags of $𝒯,$ assigns a set of vertices of $G$ to every node of $T$ such that ${\bigcup }_{t\in V(T)}\beta (t)=V(G),$ for every $e\in E(G)$ there is $t\in V(T)$ with $e\subseteq \beta (t),$ and for every $v\in V(G)$ the set $\{t\in V(T)\mid v\in \beta (T)\}$ is connected. The adhesion of $𝒯$ is ${\max }_{dt\in E(T)}|\beta (d)\cap \beta (t)|$ and the width of $𝒯$ is defined as ${\max }_{t\in V(T)}|\beta (t)|-1.$ The treewidth of a graph $G,$ denoted by $\mathrm{𝗍𝗐}(G),$ is the smallest integer $k$ such that there is a tree-decomposition of width at most $k$ for $G.$

Our next theorem generalizes a theorem of Marx, Seymour, and Wollan [37] (see also [26]). Let $q\ge 1$ be an integer. A $(q,k)$-segregated grid is a $q$-colorful graph $(G,\chi )$ where $G$ is the $(qk\times qk)$-grid where the vertices of the first column can be numbered as $v_1,\mathrm{\dots },v_{qk}$ in order of their appearance, and we have $\chi (u)=\mathrm{\varnothing }$ for all $u\in V(G)\setminus \{v_1,\mathrm{\dots },v_{qk}\}$ and there exists a permutation $\pi$ of $[q]$ such that for every $i\in [q],$ $\chi (\{v_j\mid j\in [(i-1)q+1,iq]\})=\{\pi (i)\}.$ In this situation, we say that $(G,\chi )$ realizes $\pi$. See Figure 2 for an example.

Theorem 2 shows that every $(H,\psi )$-colorful minor-free colorful graph can be turned into a collection of restricted graphs by deleting an $H^{\prime }$-minor-free subgraph. Segregated grids capture exactly the situation where we require $H^{\prime }$ to be a planar graph. We may express this in form of a parameter as follows. The torso treewidth of a $q$-colorful graph $(G,\chi )$ is the smallest integer $k$ such that there exists a set $X\subseteq V(G)$ such that the treewidth of the torso of $X$ in $G$ is at most $k$ and for every component $J$ of $G-X$ the $q$-colorful graph $(J,\chi )$ is restricted.

The second part of the first outcome is technically not necessary for the structural statement but serves as a pointer to this min-max relation. Moreover, the min-max relation itself also supplies a guarantee for the approximation of torso treewidth via the algorithm from Theorem 3.

Notice that Theorem 3 is optimal in the sense that the torso treewidth of segregated grids is unbounded. In other words, Theorem 3 can be seen as a min-max duality theorem for segregated grids. We remark that for the case $q=1,$ the torso treewidth of $(G,\chi )$ has been independently defined by Jansen and Swennenhuis [27] and by Hodor, La, Micek, and Rambaud [26] under different names.

It is easy to see that Theorem 3 is far from a structure theorem for $q$-colorful graphs that exclude an arbitrary planar colorful minor. This is in stark contrast to the $0$-colorful case provided by the Grid Theorem [48]. It turns out that, in order to fully describe the structure of $q$-colorful graphs that exclude a fixed but arbitrary planar colorful minor, we need the full power of Robertson and Seymour’s Graph Minor Structure Theorem (GMST) [52, 30, 23]. The definitions necessary to state the GMST are rather involved and technical and are ommited in this extended abstract.

We say that a graph $G$ has a $k$-near embedding in a surface $\mathrm{\Sigma }$ if there exists $A\subseteq V(G)$ with $|A|\le k$ such that $G-A=G_0\cup G_1\cup \mathrm{\cdots }\cup G_{\mathrm{\ell }},$ $\mathrm{\ell }\le k,$ such that $G_0$ has an embedding into $\mathrm{\Sigma }$ with $\mathrm{\ell }$ pairwise vertex-disjoint faces $F_i$ such that for all $i\in [\mathrm{\ell }],$ $V(G_0)\cap V(G_i)=V(F_i),$ the $G_i$’s are pairwise vertex-disjoint for positive $i,$ and for each $i\in [\mathrm{\ell }],$ $G_i$ has a path-decomposition $(P_i,{\beta }_i)$⁶⁶6A path-decomposition of a graph is a tree-decomposition $(T,\beta )$ where $T$ is a path. of width at most $k$ such that $V(P_i)=V(F_i),$ the vertices of $P_i$ appear in agreement to their cyclic ordering on the boundary of $F_i,$ and $v\in {\beta }_i(v),$ for all $v\in V(F_i).$ The set $A$ is called the apex set, the graphs $G_i,$ $i\in [\mathrm{\ell }],$ are called the vortices, and the sets $V(G_i)\setminus V(F_i)$ are the interiors of the vortices.

In the context of $q$-colorful graphs, we need some additional information regarding the colors. Let $(T,\beta )$ be a tree decomposition of a $q$-colorful graph $(G,\chi ).$ The colorful torso $(G_t,{\chi }_t)$ of $(G,\chi )$ at a node $t\in V(T)$ is the colorful graph obtained from $(G[\beta (t)],\chi )$ by turning, for every $dt\in E(T),$ the set $\beta (d)\cap \beta (t)$ into a clique and adding $\chi ({\bigcup }_{h\in V(T_d)}(\beta (h)\setminus \beta (t)))$ to $\chi (v)$ for all $v\in \beta (d)\cap \beta (t)$ where $T_d$ is the unique component of $T-dt$ that contains $d.$

Notice that Theorem 4 can also be seen as a min-max duality as implied by results of Thilikos and Wiederrecht [57].

To rephrase Theorem 4, the absence of a rainbow grid as a colorful minor implies that, with respect to any large grid minor in $G$, and in the absence of a large clique minor, there is always at least one color of small bidimensionality; moreover, all vertices of such colors can be confined to the apex set and the vortices of a near-embedding.

In particular, for $1$-colorful graphs, all colored vertices are confined entirely to the vortices and the apex set, while the surface part of the near-embedding contains no colored vertices. This appears to be a far-reaching generalization of the idea of covering all colored vertices in a planar graph by a bounded number of faces.

We believe that this provides a theoretical foundation for why many problems that are tractable on planar graphs when their annotated set is covered by few faces remain tractable on all colorful minor-closed classes of $1$-colorful graphs that exclude some fixed planar $1$-colorful graph. Moreover, it suggests that, in algorithm design, vortices in $k$-near embeddings may play a role analogous to that played by faces in planar graphs.

We say that a $q$-colorful graph $(H,\psi )$ has the Erdős-Pósa property if there exists a function $f:\mathbb{N}\to \mathbb{N}$ such that for every $k,$ every $q$-colorful graph $(G,\chi )$ either has $k$ pairwise vertex-disjoint $q$-colorful subgraphs, each containing $(H,\psi )$ as a colorful minor, or there is a set $S\subseteq V(G)$ with $|S|\le f(k)$ such that $(G-S,\chi )$ does not contain $(H,\psi )$ as a colorful minor.

It follows directly from a construction by Robertson and Seymour [48] that if a pair $(H,\psi )$ has the Erdős-Pósa property, then the graph $H$ must be planar. We prove that the boundary between instances that do and do not exhibit the Erdős-Pósa property shifts in subtle ways in the presence of colors – subtleties that are worth highlighting.

For every $q\in \mathbb{N},$ we provide the full list of graphs ${𝒪}_q$ such that a $q$-colorful graph has the Erdős-Pósa property if and only if it does not contain any of the graphs from ${𝒪}_q$ as a colorful minor. In other words, we provide, for every $q,$ the set of colorful minor-obstructions for the Erdős-Pósa property of $q$-colorful graphs. We also stress that $|{𝒪}_q|\in 𝒪(q^4),$ i.e., its size grows polynomially in the number of colors. Figure 3 gives a schematic definition of ${𝒪}_q,$ for every $q.$

Theorem 5 illustrates that the excluded minors for $q$-colorful graphs do not need to have all $q$ colors. In fact ${𝒪}_q$ contains graphs without any colored vertices and no member of ${𝒪}_q$ has five colors no matter the choice of $q.$ Our results on the Erdős-Pósa property indicate that colorful minors are a proper generalization of the concept of minors, able to express a variety of different properties.

With Theorem 3 and Theorem 4 in hand, it becomes apparent that there are fundamentally distinct ways to extend a graph parameter to a colorful analogue, and that these choices can lead to remarkably different structural decompositions. Which extension should be regarded as “canonical” appears to depend strongly on the intended application and on the structural/algorithmic consequences one wishes to capture.

For instance, from the perspective of structural decompositions, torso treewidth emerges as a particularly natural analogue of treewidth, and this is further supported by the fact that it delineates the Erdős–Pósa property for colorful minors as Theorem 5 shows, mirroring the role played by treewidth in the uncolored setting. In contrast, when viewed through the lens of obstructions, bidimensionality provides the appropriate analogue, as it yields the correct structure theorem for colorful graphs excluding an arbitrary colorful planar graph as a colorful minor, and potentially, the correct structural parameterization to obtain precise dichotomy complexity results for problems on colorful graphs that become NP-hard in planar graphs, as previously discussed.

These observations point towards a broader, open-ended research direction, which is to better understand these phenomena by examining other classical graph parameters beyond treewidth, and by developing general principles for lifting such parameters to colorful analogues. We return to this perspective in Section 1.4, where we discuss this issue in more detail and propose a conjecture.

One of the ground-breaking results of Robertson and Seymour’s Graph Minors Series is the Graph Minor Algorithm that allows to check if a graph $H$ is a minor of a graph $G$ in time ${𝒪}_{|H|}({|G|}^3)$ [51] (see [31, 33] for improvements). This algorithm also solves a rooted version of the Minor Checking problem which, as a special case, contains the so-called $k$-Disjoint Paths problem.

The $q$-Colorful Minor Checking problem has as input two $q$-colorful graphs $(G,\chi )$ and $(H,\psi ),$ and the task is to determine whether $(G,\chi )$ contains $(H,\psi )$ as a colorful minor.

We present a simple reduction to the rooted minor checking problem which allows us to leverage the algorithm of Korhonen, Pilipczuk, and Stamoulis [33] in order to deduce a similar result for $q$-Colorful Minor Checking.

Theorems 1 and 6 imply that the recognition problem for any proper colorful minor-closed class can be solved in polynomial time. We present below a parametric variant of this, based on the general framework introduced by Fellows and Langston [17, 18] for the existence of fixed-parameter tractable algorithms.

A ($q$-colorful) graph parameter is a map $𝗉$ assigning a non-negative integer to every ($q$-colorful) graph. We say that a $q$-colorful graph parameter $𝗉$ is colorful minor-monotone if for every $q$-colorful graph $(G,\chi )$ and every colorful minor $(H,\psi )$ of $(G,\chi )$ we have $𝗉(H,\psi )\le 𝗉(G,\chi ).$ Again, combining Theorems 1 and 6 we can deduce the following.

We stress that the result of Theorem 7 is not constructive, i.e., it does not give any way to construct the claimed algorithm, as is is based on the finiteness of the obstruction set of the class $\{(G,\chi )\mid 𝗉(G,\chi )\le k\},$ which is only existentially provided by Theorem 1.

Our two algorithmic results can be seen as extensions of Courcelle’s Theorem and of a recent result due to Sau, Stamoulis, and Thilikos [54] to colorful graphs. While the structural parameters in these theorems are treewidth, denoted by $\mathrm{𝗍𝗐}$ and Hadwiger number, denoted by $\mathrm{𝗁𝗐}$ (that is the maximum size of a clique minor) respectively, we now introduce two parameters on colorful graphs that serve as our new combinatorial restrictions.

A key condition for applying our algorithmic results is the notion of folio-representability of a class of colorful graphs $𝒞$ (i.e., the yes-instances of some algorithmic problem).

Informally, $𝒞$ is folio-representable if one can efficiently replace a subgraph $P$ of a colorful graph $(G,\chi )$ with colored vertices only within a small subset $B$ of the vertices of $G$ – viewed as a “protuberance”⁷⁷7We use the term protuberance to distinguish it from the term “protrusion” introduced in [4], where similar replacement operations were applied. Unlike protrusions, which are required to have bounded treewidth, protuberances are characterized by being “internally colorless”. interacting with the rest of the graph via the “boundary” $B$ – by a bounded-size subgraph $P^{\prime },$ such that the resulting graph $(G^{\prime },\chi )$ belongs to $𝒞$ if and only if $(G,\chi )$ does.

This replacement is guided by a notion of folio-equivalence: $P$ and $P^{\prime }$ must have the same set of rooted topological minors (up to a given size), with respect to the specified boundary $B.$ Efficient computation of such replacements is enabled by results from [25], making folio-representability a natural combinatorial condition for the class $𝒞.$

In what follows, whenever we refer to 1-colorful graphs we may alternatively use the notation $(G,X)$ instead of $(G,\chi )$ where $X≔{\chi }^{-1}(1)$. Given a graph $G$ and a set $X\subseteq V(G)$, we define the monodimensionality of $X$ in $G$ as the maximum order of a $(1,k)$-segregated grid colorful minor of $(G,X).$ Given a $q$-colorful graph $(G,\chi )$ and a color $i\in [q]$ we define the monodimensionality of $i$ in $(G,\chi )$ as the monodimensionality of ${\chi }^{-1}(i)$ in $G.$

We now give the logical conditions under which our framework operates. In our first result, we require the class $𝒞$ to be definable in Counting Monadic Second-Order Logic⁸⁸8There exists a formula $\varphi \in \mathrm{𝖢𝖬𝖲𝖮}$ such that $(G,\chi )\in 𝒞$ if and only if $(G,\chi )$ models $\varphi .$ (CMSO). Courcelle’s Theorem says that, for every graph class $𝒢$ definable by some CMSO-formula $\varphi ,$ membership in $𝒢$ can be decided in time ${𝒪}_{|\varphi |+\mathrm{𝗍𝗐}(G)}(|G|).$ We prove the following analogue for colorful graphs.

From Theorem 3, the maximum monodimensionality of a color in a $q$-colorful graph $(G,\chi )$ is equivalent to the maximum torso treewidth of $(G,{\chi }^{-1}(i))$ over all colors $i\in [q].$ Notice that Theorem 8 can be restated by setting $k$ to be this equivalent quantity, which plays the same role for colorful graphs as treewidth does for graphs in Courcelle’s Theorem.

For our second result, we consider a fragment of $\mathrm{𝖢𝖬𝖲𝖮}$ denoted as $\mathrm{𝖢𝖬𝖲𝖮}/\mathrm{𝗍𝗐}+\mathrm{𝖽𝗉}.$ In this logic, quantification is restricted to sets of bounded bidimensionality, and a special predicate $\mathrm{𝖽𝗉}(t_1,\mathrm{\dots },t_r,s_1,\mathrm{\dots },s_r)$ is available, asserting the existence of $r$ vertex-disjoint paths connecting the pairs $(t_1,s_1),\mathrm{\dots },(t_r,s_r).$ It was shown by Sau, Stamoulis, and Thilikos [54] that if a graph class $𝒢$ is definable in $\mathrm{𝖢𝖬𝖲𝖮}/\mathrm{𝗍𝗐}+\mathrm{𝖽𝗉},$ then membership in $𝒢$ can be decided in time ${𝒪}_{|\varphi |+\mathrm{𝗁𝗐}(G)}({|G|}^2)$.

The Hadwiger number of a color $i$ in a $q$-colorful graph $(G,\chi )$ is the maximum $k$ for which $(G,{\chi }^{-1}(i))$ contains the rainbow $k$-clique as a colorful minor. We prove the following.

We emphasize that the applicability of Theorems 8 and 9, based on the structural theorems Theorems 2 and 3 respectively, exceeds the scope of Courcelle’s Theorem and the results of [54]. The generality of our extension is displayed by the fact that, for every $q\ge 1$, there are classes of $q$-colorful graphs $(G,\chi )$ for which the maximum monodimensionality/Hadwiger number of a color in $(G,\chi )$ is bounded while the treewidth/Hadwiger number of $G$ is unbounded.

This is a strong indication that, for problems on colorful graphs, the appropriate structural parameterizations toward deriving (meta-)algorithmic results should take into account the way the colors are distributed in the inputs.

We derive Theorems 8 and 9 as special cases of a more general result applicable to optimization problems.

The genuinely new difficulties and contributions arise in outcome (a.i). In the colored settings, the mere presence of a large clique-minor provides little information on the structure of the colorful graph with respect to the colored vertices. For our purposes, it is therefore essential to understand how well the colored vertices are connected to this clique-minor. Concretely, given a $q$-colorful graph $(G,\chi )$ containing a large clique-minor, we aim to establish the following dichotomy:

1. b.i)

   there exists a small set of vertices $S$ and a color $i\in [q]$ such that the component of $(G-S,\chi )$ containing most of the clique-minor is free of vertices of color $i,$ or

2. b.ii)

   $(G,\chi )$ contains a large rainbow clique-minor that is highly connected to the original clique-minor.

This result constitutes a central new ingredient underpinning all our structural theorems.

In the context of the Disjoint Paths problem, a similar result was established by Robertson and Seymour [51] for $1$-colorful graphs with a bounded number of colored vertices. Our setting is substantially more general: we allow $q$-colorful graphs with an arbitrary number of colored vertices. Our proof involves a one-to-many strengthening of Menger’s Theorem which may be of independent interest. For all positive integers $k,\mathrm{\ell }$, given vertex sets $X_1,\mathrm{\dots },X_{\mathrm{\ell }}$ and $Y$ in a graph $G,$ either

1. c.i)

   there exist $k\cdot \mathrm{\ell }$ disjoint paths in $G,$ with exactly $k$ paths linking $X_i$ to $Y,$ or

2. c.ii)

   there exists an index $i\in [l]$ and a vertex set $S$ of size less than $k\cdot \mathrm{\ell }$ that separates $X_i$ from $Y.$

Interestingly, our results on the Erdős-Pósa property for colorful minors imply that even a two-to-two strengthening of Menger’s theorem cannot hold in general, not even approximately. Consequently, our structural results are in a sense “tight”, as we cannot expect to replace condition (b.i) with a stronger alternative.

It is noteworthy that in the local version of Theorem 3, outcome (a.ii) also relies on the one-to-many strengthening of Menger above to control how well-connected the colored vertices are to a given flat wall in the graph.

Erdős-Pósa-type dualities in graph minors and beyond are intrinsically related to structural characterization of restricted classes of graphs, often in terms of “global” decomposition theorems based on tree-decompositions. A prime example of this interaction is the celebrated characterization of the proper minor-closed classes which have the Erdős-Pósa property for minors, shown by Robertson and Seymour [48] to be precisely those of bounded treewidth.

Crucial to this duality is showing that graph classes of unbounded treewidth necessarily fail to satisfy the Erdős–Pósa property. By the grid theorem, such classes are precisely those containing all planar graphs. Consequently, this reduces to understanding why the two Kuratowski minors $K_5$ and $K_{3,3}$ themselves do not admit the Erdős–Pósa property. In [48], Robertson and Seymour address this by constructing families of graphs based on $K_5$ and $K_{3,3}$ that explicitly violate the Erdős–Pósa property. These constructions are inherently topological: The resulting graphs embed minimally in the torus or the projective plane, but not in the sphere. At a high level, the argument exploits the additivity of Euler-genus under disjoint union [38], which implies that repeatedly combining non-planar graphs forces unbounded Euler-genus.

In the colorful setting, we initially follow the same high-level strategy. We identify torso treewidth as the correct parameter governing the Erdős–Pósa property for colorful minors. Utilizing our grid theorem for torso treewidth (Theorem 3), we identify the set ${𝒪}_q$ of $q$-colorful graphs and for the reverse direction of Theorem 5, we have to show that each $q$-colorful graph in ${𝒪}_q,$ violates the Erdős–Pósa property for colorful minors.

At this point, however, the classical approach breaks down. Unlike the uncolored case, most graphs in ${𝒪}_q$ are planar with particular assumptions on the topology induced by the colored vertices. As a consequence, the standard arguments are no longer applicable, as they fundamentally rely on non-planar embeddings.

Instead, our arguments crucially exploit the distribution of colored vertices within these graphs. We show that the topology induced by this distribution – rather than by the underlying graph alone – can still be leveraged to construct families that violate the Erdős–Pósa property. Once more, this highlights the importance of the arrangement of colored vertices within the underlying graph.