Delphi.science

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

Evangelos Protopapas, Dimitrios M. Thilikos, Sebastian Wiederrecht

arXivarxiv/2609.04956Sep 4, 2026math.COscore 0

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…

SourceJSON

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2609.04956
curl -X POST /api/v1/records/arxiv/2609.04956/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.04956/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'