1 citations · 1 across the 10 of their papers we have counts for
11 papers
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…
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…
On non-planar, cycle-conformal graphs
Maximilian Gorsky, Clemens Kuske
A graph is called matching covered if all of its edges are contained in some perfect matching of . Furthermore, a cycle is called conformal if has…
The price of homogeneity is polynomial
Maximilian Gorsky, Michał T. Seweryn, Sebastian Wiederrecht
We provide explicit and polynomial bounds for the Homogeneous Wall Lemma which occurred for the first time implicitly in the th entry of Robertson and Seymour's Graph Minors Se…
Odd-Cycle-Packing-treewidth: On the Maximum Independent Set problem in odd-minor-free graph classes
Mujin Choi, Maximilian Gorsky, Gunwoo Kim +2
We introduce the tree-decomposition-based graph parameter Odd-Cycle-Packing-treewidth (OCP-tw) as a width parameter that asks to decompose a given graph into pieces of bounded odd…
Catching Rats in -minor-free Graphs
Maximilian Gorsky, Giannos Stamoulis, Dimitrios M. Thilikos +1
We show that every -minor-free graph that also excludes a -grid as a minor has treewidth/branchwidth bounded from above by a function that is linear in $k…
Polynomial Bounds for the Graph Minor Structure Theorem
Maximilian Gorsky, Michał T. Seweryn, Sebastian Wiederrecht
The Graph Minor Structure Theorem, originally proven by Robertson and Seymour [JCTB, 2003], asserts that there exist functions such that…
A note on the 2-Factor Hamiltonicity Conjecture
Maximilian Gorsky, Theresa Johanni, Sebastian Wiederrecht
The 2-factor Hamiltonicity Conjecture by Funk, Jackson, Labbate, and Sheehan [JCTB, 2003] asserts that all cubic, bipartite graphs in which all 2-factors are Hamiltonian cycles can…
Packing even directed circuits quarter-integrally
Maximilian Gorsky, Ken-ichi Kawarabayashi, Stephan Kreutzer +1
We prove the existence of a computable function such that for every integer and every digraph either contains a collection of…
Matching Theory and Barnette's Conjecture
Maximilian Gorsky, Raphael Steiner, Sebastian Wiederrecht
Barnette's Conjecture claims that all cubic, 3-connected, planar, bipartite graphs are Hamiltonian. We give a translation of this conjecture into the matching-theoretic setting. Th…
Differential games, locality and model checking for FO logic of graphs
Jakub Gajarský, Maximilian Gorsky, Stephan Kreutzer
We introduce differential games for FO logic of graphs, a variant of Ehrenfeucht-Fraïssé games in which the game is played on only one graph and the moves of both players restricte…