30 citations · 157 across the 83 of their papers we have counts for
39 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…
Obstructions for Minor-Closed Classes of limiting Densities Below 3/2
Antonios Kominatos, Reem Mahmoud, Dimitrios M. Thilikos
Given a graph class , the limiting density of is defined as where $\mathsf{ex}(\mathcal{G…
Optimal Bounds for the k-Disjoint Paths Problem
Dario Cavallaro, Maximilian Gorsky, Stephan Kreutzer +2
The Graph Minors Series of Robertson and Seymour forms the foundation of algorithmic structural graph theory, yielding fixed-parameter algorithms for problems such as Disjoint Path…
Excluding surfaces as minors in graphs
Dimitrios M. Thilikos, Sebastian Wiederrecht
The Graph Minors Structure Theorem (GMST) of Robertson and Seymour states that for every graph any -minor-free graph has a tree-decomposition of bounded adhesion such t…
Plane Strong Connectivity Augmentation
Stéphane Bessy, Daniel Gonçalves, Amadeus Reinald +1
We investigate the problem of strong connectivity augmentation within plane oriented graphs. We show that deciding whether a plane oriented graph can be augmented with (any num…
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…