Pith. sign in

REVIEW 1 cited by

A tight Erd\H{o}s-P\'osa function for planar minors

Not yet reviewed by Pith; the record is open.

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 1807.04969 v5 pith:L5PFQMDU submitted 2018-07-13 math.CO cs.DM

classification math.COcs.DM
keywords mathbbminorconstantcontainingfunctionplanarresultsome
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
abstract

Let $H$ be a planar graph. By a classical result of Robertson and Seymour, there is a function $f:\mathbb{N} \to \mathbb{R}$ such that for all $k \in \mathbb{N}$ and all graphs $G$, either $G$ contains $k$ vertex-disjoint subgraphs each containing $H$ as a minor, or there is a subset $X$ of at most $f(k)$ vertices such that $G-X$ has no $H$-minor. We prove that this remains true with $f(k) = c k \log k$ for some constant $c=c(H)$. This bound is best possible, up to the value of $c$, and improves upon a recent result of Chekuri and Chuzhoy [STOC 2013], who established this with $f(k) = c k \log^d k$ for some universal constant $d$. The proof is constructive and yields a polynomial-time $O(\log \mathsf{OPT})$-approximation algorithm for packing subgraphs containing an $H$-minor.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Erd\H{o}s-P\'osa property of rooted tree minors

    math.CO 2026-07 accept novelty 7.0 of 10

    Rooted tree minors satisfy a linear Erdős-Pósa bound: k vertex-disjoint rooted models or a hitting set of O(k) vertices.

Pith tools