Forbidding anticomplete planar minors: Induced Erdős--Pósa property and Maximum Independent Set in QP
The Erdős--Pósa theorem asserts that every graph $G$ with no $k$ disjoint cycles contains a set $X$ of $f(k)$ vertices such that $G\setminus X$ has no cycle. Robertson and Seymour showed that this Erdős--Pósa property also holds for $H$-minor models of any planar graph $H$. Equivalently, if $G$ has no $k$ minor models of $H$ pairwise at distance at least 1 (i.e. disjoint), then one can remove $f(k,H)$ balls of radius 0 (i.e. vertices) to make the graph $H$-minor free. We show that this coarse graph theory point of view generalizes to distance at least 2 versus radius 1 balls, yielding the…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2607.09646
curl -X POST /api/v1/records/arxiv/2607.09646/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.09646/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'