12 papers
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…
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…
An Overview of Universal Obstructions for Graph Parameters
Christophe Paul, Evangelos Protopapas, Dimitrios M. Thilikos
In a recent work, we introduced a parametric framework for obtaining obstruction characterizations of graph parameters with respect to a quasi-ordering on graphs. Towar…
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…
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…