Matthias Heinlein

dblp:204/8844 · DBLP profile ↗
← Back
2ranked-venue papers
0as first author
1since 2021 · last 2021
—ORCID · none

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 2 · 1 since 2021
YearPublicationVenuePosition
2021 K4-Subdivisions Have the Edge-Erdös-Pósa Property
abstract
We prove that every graph $G$ contains either $k$ edge-disjoint $K_4$-subdivisions or a set $X$ of at most $\ensuremath{O}(k^8 \log k)$ edges such that $G-X$ does not contain any $K_4$-subdivision. This shows that $K_4$-subdivisions have the edge-Erdös--Pósa property.
Henning Bruhn, Matthias Heinlein
SIAM J. Discret. Math.2
2018 Frames, A-Paths, and the Erdös-Pósa Property
abstract
A key feature of Simonovits' proof of the classic Erdös--Pósa theorem is a simple subgraph of the host graph, a frame, that determines the outcome of the theorem. We transfer this frame technique to $A$-paths. With it we deduce a simple proof of Gallai's theorem, although with a worse bound, and we verify the Erdös--Pósa property for long and for even $A$-paths. We also show that even $A$-paths do not have the edge-Erdös--Pósa property.
Henning Bruhn, Matthias Heinlein, Felix Joos
SIAM J. Discret. Math.2