5 citations · 6 across the 11 of their papers we have counts for
12 papers · 1 filter
The Erdős-Pósa Property for Colorful Minors
Evangelos Protopapas, Dimitrios M. Thilikos, Sebastian Wiederrecht
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 proble…
A coarse block-cut tree theorem
Júlia Baligács, Václav Blažej, Jadwiga Czyżewska +2
We prove a coarse analogue of the classic fact that every graph can be decomposed along its cut-vertices into -connected components. Precisely, we prove that for every graph …
A coarse Menger's Theorem for planar and bounded genus graphs
Václav Blažej, Michał Pilipczuk, Evangelos Protopapas
Menger's Theorem is a fundamental result in graph theory. It states that if in a graph with distinguished sets of terminal vertices and there are no pairwise vertex…
Quickly excluding an annotated planar graph
Maximilian Gorsky, Evangelos Protopapas, Sebastian Wiederrecht
We provide proofs certifying that the structure theorem for vertex sets of bounded bidimensionality holds with polynomial bounds. The bidimensionality of vertex sets is a common ge…
Colorful Minors
Evangelos Protopapas, Dimitrios M. Thilikos, Sebastian Wiederrecht
We introduce the notion of colorful minors, which generalizes the classical concept of rooted minors in graphs. A -colorful graph= is defined as a pair where is a…
The Local Structure Theorem for Graph Minors with finite index
Christophe Paul, Evangelos Protopapas, Dimitrios M. Thilikos +1
The Local Structure Theorem (LST) for Graph Minors roughly states that for every -minor-free graph that contains a sufficiently large wall , there is a small vertex subse…
Excluding Pinched Spheres
Laure Morelle, Evangelos Protopapas, Dimitrios M. Thilikos +1
The pinched sphere is the pseudo-surface obtained by identifying two distinct points of the sphere. We provide a structural characterization of graphs exclud…
Generating strongly 2-connected digraphs
Meike Hatzel, Stephan Kreutzer, Evangelos Protopapas +3
We prove that there exist four operations such that given any two strongly -connected digraphs and where is a butterfly-minor of , there exists a sequence $D_0,\d…
Obstructions to Erdős-Pósa Dualities for Minors
Christophe Paul, Evangelos Protopapas, Dimitrios M. Thilikos +1
Let and be minor-closed graph classes. The pair is an Erdős-Pósa pair (EP-pair) if there is a function where, for every and ever…
Delineating Half-Integrality of the Erdős-Pósa Property for Minors: the Case of Surfaces
Christophe Paul, Evangelos Protopapas, Dimitrios M. Thilikos +1
In 1986 Robertson and Seymour proved a generalization of the seminal result of Erdős and Pósa on the duality of packing and covering cycles: A graph has the Erdős-Pósa property for…
Graph Parameters, Universal Obstructions, and WQO
Christophe Paul, Evangelos Protopapas, Dimitrios M. Thilikos
We establish a parametric framework for obtaining obstruction characterizations of graph parameters with respect to a quasi-ordering on graphs. At the center of this fr…
On Strict Brambles
Emmanouil Lardas, Evangelos Protopapas, Dimitrios M. Thilikos +1
A strict bramble of a graph is a collection of pairwise-intersecting connected subgraphs of The order of a strict bramble is the minimum size of a set of vertic…