5 papers
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…
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…
Face covers and rooted minors in bounded genus graphs
Samuel Fiorini, Stefan Kober, Michał T. Seweryn +2
A {\em rooted graph} is a graph together with a designated vertex subset, called the {\em roots}. In this paper, we consider rooted graphs embedded in a fixed surface. A collection…
Half-integral Erdős-Pósa property for non-null - paths
Vera Chekan, Colin Geniet, Meike Hatzel +4
For a group , a -labelled graph is an undirected graph where every orientation of an edge is assigned an element of so that opposite orientations of the same edge are…
Integer programs with nearly totally unimodular matrices: the cographic case
Manuel Aprile, Samuel Fiorini, Gwenaël Joret +4
It is a notorious open question whether integer programs (IPs), with an integer coefficient matrix whose subdeterminants are all bounded by a constant in absolute value, ca…