20 citations · 180 across the 43 of their papers we have counts for
8 papers · 1 filter
A polynomial kernel for -leaf power deletion
Jungho Ahn, Eduard Eiben, O-joung Kwon +1
For a non-negative integer , the -leaf power of a tree is a simple graph on the leaves of such that two vertices are adjacent in if and only if their di…
Obstructions for bounded shrub-depth and rank-depth
O-joung Kwon, Rose McCarty, Sang-il Oum +1
Shrub-depth and rank-depth are dense analogues of the tree-depth of a graph. It is well known that a graph has large tree-depth if and only if it has a long path as a subgraph. We…
The grid theorem for vertex-minors
Jim Geelen, O-Joung Kwon, Rose McCarty +1
We prove that, for each circle graph , every graph with sufficiently large rank-width contains a vertex-minor isomorphic to .
Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth
Eduard Eiben, Robert Ganian, Thekla Hamm +1
We develop a framework for applying treewidth-based dynamic programming on graphs with "hybrid structure", i.e., with parts that may not have small treewidth but instead possess ot…
Graphs without two vertex-disjoint -cycles
Minjeong Kang, O-joung Kwon, Myounghwan Lee
Lovász (1965) characterized graphs without two vertex-disjoint cycles, which implies that such graphs have at most three vertices hitting all cycles. In this paper, we ask whether…
Graphs of bounded depth- rank-brittleness
O-joung Kwon, Sang-il Oum
We characterize classes of graphs closed under taking vertex-minors and having no and no disjoint union of copies of the -subdivision of for some . Our ch…
Erdös-Pósa property of minor-models with prescribed vertex sets
O-joung Kwon, Dániel Marx
A minor-model of a graph in a graph is a subgraph of that can be contracted to . We prove that for a positive integer and a non-empty planar graph with at…
Branch-depth: Generalizing tree-depth of graphs
Matt DeVos, O-joung Kwon, Sang-il Oum
We present a concept called the branch-depth of a connectivity function, that generalizes the tree-depth of graphs. Then we prove two theorems showing that this concept aligns clos…