4 papers
An Erdős-Pósa theorem for cycles and faces of distinct lengths
J. Pascal Gollin, Maximilian Gorsky, Meike Hatzel +6
We show that for every , every graph contains vertex-disjoint cycles of different lengths, or there exists a set with $|X| \in \mathcal…
The Erdős-Pósa property for prime-length cycles fails (and beyond)
Maximilian Gorsky, Kevin Hendrey, Tony Huynh
We prove that for every , prime-length cycles do not have the -integral Erdős-Pósa property, even when restricted to planar graphs. We in fact prove…
Triangulated spheres with holes in triangulated surfaces
Katie Clinch, Sean Dewar, Niloufar Fuladi +6
Let denote a sphere with holes. Given a triangulation of a surface , we consider the question of when contains a spanning subgraph such t…
Computing the forcing spectrum of outerplanar graphs in polynomial time
Maximilian Gorsky, Fabian Kreßin
The forcing number of a graph with a perfect matching is the minimum number of edges in whose endpoints need to be deleted, such that the remaining graph only has a single…