15 citations · 28 across the 8 of their papers we have counts for
12 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…
Erdős-Pósa property for induced packings of long -cycles
Jungho Ahn, O-joung Kwon
The Erdős-Pósa theorem states that for every integer , every graph contains either vertex-disjoint cycles or a set of vertices meeting all cycles…
Optimal b-Colourings and Fall Colourings in -Free Graphs
Jungho Ahn, Tala Eagling-Vose, Felicia Lucke +3
In a colouring of a graph, a vertex is b-chromatic if it is adjacent to a vertex of every other colour. We consider four well-studied colouring problems: b-Chromatic Number, Tight…
Unavoidable pivot-minors in graphs of large rank-depth
Jungho Ahn, Kevin Hendrey, O-joung Kwon +1
Shrub-depth and rank-depth are related graph parameters that are dense analogs of tree-depth. We prove that for every positive integer , every graph of sufficiently large rank-d…
A coarse Erdős-Pósa theorem
Jungho Ahn, J. Pascal Gollin, Tony Huynh +1
An induced packing of cycles in a graph is a set of vertex-disjoint cycles with no edges between them. We generalise the classic Erdős-Pósa theorem to induced packings of cycles. M…
Twin-width of subdivisions of multigraphs
Jungho Ahn, Debsoumya Chakraborti, Kevin Hendrey +1
For each , we construct a finite set of multigraphs such that for each graph of girth at least obtained from a multigraph by subdividing each edge at leas…
The proper conflict-free -coloring problem and the odd -coloring problem are NP-complete on bipartite graphs
Jungho Ahn, Seonghyuk Im, Sang-il Oum
A proper coloring of a graph is \emph{proper conflict-free} if every non-isolated vertex has a neighbor whose color is unique in the neighborhood of . A proper coloring of a…
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…
Bounds for the Twin-width of Graphs
Jungho Ahn, Kevin Hendrey, Donggyu Kim +1
Bonnet, Kim, Thomassé, and Watrigant (2020) introduced the twin-width of a graph. We show that the twin-width of an -vertex graph is less than $(n+\sqrt{n\ln n}+\sqrt{n}+2\ln n)…
Towards constant-factor approximation for chordal / distance-hereditary vertex deletion
Jungho Ahn, Eun Jung Kim, Euiwoong Lee
For a family of graphs , Weighted -Deletion is the problem for which the input is a vertex weighted graph and the goal is to delete $S\subseteq…
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…
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…