20 citations · 180 across the 43 of their papers we have counts for
59 papers
An Erdős-Pósa theorem for induced packings of even cycles
Jungho Ahn, Lars Jaffke, O-joung Kwon +2
We show that for every graph and every positive integer , contains either vertex-disjoint even cycles with no edges between distinct cycles, or a set of $O(k^2\log k…
On a variant of dichromatic number for digraphs with prescribed sets of arcs
O-joung Kwon, Xiaopan Lian
In this paper, we consider a variant of dichromatic number on digraphs with prescribed sets of arcs. Let be a digraph and let be two sets of arcs in . For a subdi…
A characterization of graphs of radius- flip-width at most
Yeonsu Chang, Sejin Ko, O-joung Kwon +1
The -flip-width of a graph, for , is a graph parameter defined in terms of a variant of the cops and robber game, called the flipper game, and it…
Group vertex-arboricity of group-labelled graphs
O-joung Kwon, Xiaopan Lian
We introduce the vertex-arboricity of group-labelled graphs. For an abelian group , a -labelled graph is a graph whose edges are labelled by elements of . For an abelian g…
A new width parameter of graphs based on edge cuts: -edge-crossing width
Yeonsu Chang, O-joung Kwon, Myounghwan Lee
We introduce graph width parameters, called -edge-crossing width and edge-crossing width. These are defined in terms of the number of edges crossing a bag of a tree-cut decompos…
A unified Erdős-Pósa theorem for cycles in graphs labelled by multiple abelian groups
J. Pascal Gollin, Kevin Hendrey, O-joung Kwon +2
In 1965, Erdős and Pósa proved that there is an (approximate) duality between the maximum size of a packing of cycles and the minimum size of a vertex set hitting all cycles. Such…
Unified almost linear kernels for generalized covering and packing problems on nowhere dense classes
Jungho Ahn, Jinha Kim, O-joung Kwon
Let be a family of graphs, and let be nonnegative integers. The \textsc{-Covering} problem asks whether for a graph and an integer , t…
Reduced bandwidth: a qualitative strengthening of twin-width in minor-closed classes (and beyond)
Édouard Bonnet, O-joung Kwon, David R. Wood
In a reduction sequence of a graph, vertices are successively identified until the graph has one vertex. At each step, when identifying and , each edge incident to exactly o…
A Unifying Framework for Characterizing and Computing Width Measures
Eduard Eiben, Robert Ganian, Thekla Hamm +2
Algorithms for computing or approximating optimal decompositions for decompositional parameters such as treewidth or clique-width have so far traditionally been tailored to specifi…
Obstructions for matroids of path-width at most k and graphs of linear rank-width at most k
Mamadou Mostapha Kanté, Eun Jung Kim, O-joung Kwon +1
Every minor-closed class of matroids of bounded branch-width can be characterized by a list of excluded minors, but unlike graphs, this list may need to be infinite in general. How…
On the Erdős-Pósa property for long holes in -free graphs
Tony Huynh, O-joung Kwon
We prove that there exists a function such that for every -free graph and every , either contains vertex-disjoint…
Classes of intersection digraphs with good algorithmic properties
Lars Jaffke, O-joung Kwon, Jan Arne Telle
An intersection digraph is a digraph where every vertex is represented by an ordered pair of sets such that there is an edge from to if and only if a…
A unified half-integral Erdős-Pósa theorem for cycles in graphs labelled by multiple abelian groups
J. Pascal Gollin, Kevin Hendrey, Ken-ichi Kawarabayashi +2
Erdős and Pósa proved in 1965 that there is a duality between the maximum size of a packing of cycles and the minimum size of a vertex set hitting all cycles. Such a duality does n…
A system of disjoint representatives of line segments with given directions
Jinha Kim, Minki Kim, O-Joung Kwon
We prove that for all positive integers and , there exists an integer satisfying the following. If is a set of direction vectors in the plane and $\math…
The canonical directed tree decomposition and its applications to the directed disjoint paths problem
Archontia C. Giannopoulou, Ken-ichi Kawarabayashi, Stephan Kreutzer +1
The canonical tree-decomposition theorem, given by Robertson and Seymour in their seminal graph minors series, turns out to be one of the most important tool in structural and algo…
Tree pivot-minors and linear rank-width
Konrad K. Dabrowski, François Dross, Jisu Jeong +4
Tree-width and its linear variant path-width play a central role for the graph minor relation. In particular, Robertson and Seymour (1983) proved that for every tree~, the class…
Close relatives of Feedback Vertex Set without single-exponential algorithms parameterized by treewidth
Benjamin Bergougnoux, Édouard Bonnet, Nick Brettell +1
The Cut & Count technique and the rank-based approach have lead to single-exponential FPT algorithms parameterized by treewidth, that is, running in time , for F…
A half-integral Erdős-Pósa theorem for directed odd cycles
Ken-ichi Kawarabayashi, Stephan Kreutzer, O-joung Kwon +1
We prove that there exists a function such that every directed graph contains either directed odd cycles where every vertex of is c…
Well-partitioned chordal graphs: obstruction set and disjoint paths
Jungho Ahn, Lars Jaffke, O-joung Kwon +1
We introduce a new subclass of chordal graphs that generalizes split graphs, which we call well-partitioned chordal graphs. Split graphs are graphs that admit a partition of the ve…
Rainbow independent sets on dense graph classes
Jinha Kim, Minki Kim, O-joung Kwon
Given a family of independent sets in a graph, a rainbow independent set is an independent set such that there is an injection where fo…
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…