15 citations · 28 across the 8 of their papers we have counts for
8 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…
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…
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)…
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…