28 citations · 44 across the 32 of their papers we have counts for
5 papers · 1 filter
Unavoidable induced subgraphs in graphs with complete bipartite induced minors
Maria Chudnovsky, Meike Hatzel, Tuukka Korhonen +2
We prove that if a graph contains the complete bipartite graph as an induced minor, then it contains a cycle of length at most~12 or a theta as an induced subgraph. W…
Treewidth is Polynomial in Maximum Degree on Weakly Sparse Graphs Excluding a Planar Induced Minor
Édouard Bonnet, Jędrzej Hodor, Tuukka Korhonen +1
A graph contains a graph as an induced minor if can be obtained from after vertex deletions and edge contractions. We show that for every -vertex planar graph $H…
On Induced Versions of Menger's Theorem on Sparse Graphs
Peter Gartland, Tuukka Korhonen, Daniel Lokshtanov
Let and be sets of vertices in a graph . Menger's theorem states that for every positive integer , either there exists a collection of vertex-disjoint paths betwe…
Grid Induced Minor Theorem for Graphs of Small Degree
Tuukka Korhonen
A graph is an induced minor of a graph if can be obtained from by vertex deletions and edge contractions. We show that there is a function $f(k, d) = O(k^{10} + 2^{…
Tight Bounds for Potential Maximal Cliques Parameterized by Vertex Cover
Tuukka Korhonen
We show that a graph with vertices and vertex cover of size has at most potential maximal cliques. We also show that for each positive integer , there exists a…