7 citations · 9 across the 5 of their papers we have counts for
5 papers
Space proof complexity for random -CNFs via a -Hall's Theorem
Ilario Bonacina, Nicola Galesi, Tony Huynh +1
We investigate the space complexity of refuting -CNFs in Resolution and algebraic systems. No lower bound for refuting any family of -CNFs was previously known for the total…
An exact characterization of tractable demand patterns for maximum disjoint path problems
Dániel Marx, Paul Wollan
We study the following general disjoint paths problem: given a supply graph , a set of terminals, a demand graph on the vertices , and an integer , t…
A structure theorem for strong immersions
Zdenek Dvorak, Paul Wollan
A graph H is strongly immersed in G if H is obtained from G by a sequence of vertex splittings (i.e., lifting some pairs of incident edges and removing the vertex) and edge removal…
K_6 minors in 6-connected graphs of bounded tree-width
Ken-ichi Kawarabayashi, Serguei Norine, Robin Thomas +1
We prove that every sufficiently big 6-connected graph of bounded tree-width either has a K_6 minor, or has a vertex whose deletion makes the graph planar. This is a step toward pr…
The Erdös-Pósa property for clique minors in highly connected graphs
Reinhard Diestel, Ken-ichi Kawarabayashi, Paul Wollan
We prove the existence of a function f: N^2 -> N such that for all p,k in N every (k(p-3) + 14p+14) - connected graph either has k disjoint K_p minors or contains a set of at most…