1 citations · 1 across the 2 of their papers we have counts for
6 papers
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…
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…
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…