Research Overview
Our research in Structural Graph Theory focuses on mathematically modeling and analyzing the fundamental properties of complex networks. By studying structural parameters and decomposition techniques, we aim to understand the underlying mathematical structures of graphs. This theoretical foundation allows us to classify graphs and develop a deep understanding of their structural complexity.
Major Research Topics
1. Structural Graph Parameters & Decomposition
- Graph Parameters: Investigating structural parameters that measure graph complexity, with a particular focus on twin-width, rank-depth, treewidth, and pivot-minors.
- Decomposition & Width Measures: Studying width-based decompositions to understand the structural boundaries of computationally hard graph problems.
2. Extremal & Structural Graph Theory (Erdős-Pósa Type Results)
- Erdős-Pósa Property: Studying the duality between packing and covering of combinatorial objects (e.g., cycles, paths) in various graph classes.
- Structural Theorems: Proving fundamental structural theorems that bridge deep mathematical graph theory and theoretical computer science.
Selected Publications
- Unavoidable pivot-minors in graphs of large rank-depth Jungho Ahn, Kevin Hendrey, O-joung Kwon, and Sang-il Oum SIAM Journal on Discrete Mathematics (SIDMA), 2026.
- A coarse Erdős-Pósa theorem Jungho Ahn, Pascal Gollin, Tony Huynh, and O-joung Kwon The 36th ACM-SIAM Symposium on Discrete Algorithms (SODA 2025), 2025.
- Twin-width of random graphs Jungho Ahn, Debsoumya Chakraborti, Kevin Hendrey, Donggyu Kim, and Sang-il Oum Random Structures & Algorithms (RSA), 2024.