The Erdős-Pósa Property for Colorful Minors

@misc{protopapas2026erdőspósa,
  title = {{The Erdős-Pósa Property for Colorful Minors}},
  author = {Evangelos Protopapas and Dimitrios M. Thilikos and Sebastian Wiederrecht},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.04956},
  eprint = {2609.04956},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.04956},
}

TY  - UNPB
TI  - The Erdős-Pósa Property for Colorful Minors
AU  - Evangelos Protopapas
AU  - Dimitrios M. Thilikos
AU  - Sebastian Wiederrecht
PY  - 2026
DA  - 2026/09/04
PB  - arXiv
DO  - 10.48550/arxiv.2609.04956
UR  - https://arxiv.org/abs/2609.04956
AB  - A colorful graph relation enhances the minor relation by merging color sets along contractions and by allowing the removal of colors; it generalizes rooted minors and models problems on graphs with several, possibly overlapping, annotated vertex sets. A graph has the Erdős-Pósa property for minors if and only if it is planar, by a classical theorem of Robertson and Seymour. In this work we determine, for the colorful minor relation, exactly which colorful graphs have the Erdős-Pósa property. Our characterization takes three equivalent forms. The first is structural: the colorful graphs with the property are those that can be drawn with all their colored vertices on one face and whose colors are, in a precise sense, laid out along that face without interleaving. The second is given by an obstruction set: they are those excluding every member of an explicit infinite family 𝒪, of which only O(|I|^4) members have colors that are a subset of I, for every finite set I of colors. The third is grid-like: they are exactly the colorful minors of unions of particular families of segregated grids, the colorful analogues of the grids that drive the classical proof.
ER  -