View PDF HTML (experimental)

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. 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.

Submission history

From: Dimitrios Thilikos [view email]
[v1] Mon, 14 Jul 2025 16:46:29 UTC (350 KB)
[v2] Sat, 7 Feb 2026 08:53:18 UTC (348 KB)
[v3] Wed, 6 May 2026 08:10:07 UTC (3,102 KB)
[v4] Thu, 3 Sep 2026 17:50:41 UTC (133 KB)