21 papers
Spanning Paths and Cycles: Structural Limitations of the Irrelevant Vertex Technique
Dimitrios M. Thilikos, Sebastian Wiederrecht
The Irrelevant Vertex Technique is one of the cornerstones of algorithmic graph theory, underlying Robertson and Seymour's algorithm for \textsc{Disjoint Paths} and much of the alg…
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{…
The Graph Minor Structure Theorem through Bidimensionality
Dimitrios M. Thilikos, Sebastian Wiederrecht
The bidimensionality of a set of vertices in a graph is the maximum for which contains as a -rooted minor the -grid. This notion allows for the fol…
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…
W-state graphs: Structure and Algorithms
Rishikesh Gajjala, Saurabh Ray, Dimitrios M. Thilikos
We study the class of edge-coloured graphs arising from the graph-theoretic representation of quantum photonic experiments that generate multipartite W-states. Abstracting away phy…
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…