5 papers · 1 filter
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.…
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…