20 citations · 180 across the 43 of their papers we have counts for
35 papers · 1 filter
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 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…
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…
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…
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…
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…
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 .
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…
Classes of graphs with no long cycle as a vertex-minor are polynomially -bounded
Ringi Kim, O-joung Kwon, Sang-il Oum +1
A class of graphs is -bounded if there is a function such that for every graph and every induced subgraph of , . In ad…
A Menger-like property of tree-cut width
Archontia C. Giannopoulou, O-joung Kwon, Jean-Florent Raymond +1
In 1990, Thomas proved that every graph admits a tree decomposition of minimum width that additionally satisfies a certain vertex-connectivity condition called leanness [A Menger-l…
Scattered classes of graphs
O-joung Kwon, Sang-il Oum
For a class of graphs equipped with functions defined on subsets of or , we say that is -scattered with respect to if the…