Jungho Ahn (안정호)

Preprints

Unavoidable pivot-minors in graphs of large rank-depth
-with Kevin Hendrey, O-joung Kwon, and Sang-il Oum.

Approximating maximum cut on interval graphs and split graphs beyond Goemans-Williamson
-with Ian DeHaan, Eun Jung Kim, and Euiwoong Lee.
-arXiv:2507.10436

Finding d-cuts in claw-free graphs
-with Tala Eagling-Vose, Felicia Lucke, Daniël Paulusma, and Siani Smith.
-arXiv:2505.17993

Twin-width one
-with Hugo Jacob, Noleen Köhler, Christophe Paul, Amadeus Reinald, and Sebastian Wiederrecht.
-arXiv:2501.00991

A coarse Erdős-Pósa theorem
-with Pascal Gollin, Tony Huynh, and O-joung Kwon.
-arXiv:2407.05883

Spectral integral variation of signed graphs
-with Cheolwon Heo and Sunyo Moon.
-arxiv:2401.02639

Unified almost linear kernels for generalized covering and packing problems on nowhere dense classes
-with Jinha Kim and O-joung Kwon.
-arXiv:2207.06660

Accepted Journal Papers

Jungho Ahn, Seonghyuk Im, and Sang-il Oum, The proper conflict-free k-coloring problem and the odd k-coloring problem are NP-complete on bipartite graphs, Discrete Appl. Math. (2025).
-DOI:10.1016/j.dam.2025.06.026 / arXiv:2208.08330

Jungho Ahn, Debsoumya Chakraborti, Kevin Hendrey, and Sang-il Oum, Twin-width of subdivisions of multigraphs, SIAM J. Discrete Math. (2025).
-DOI:10.1137/23M1621514 / arXiv:2306.05334

Jungho Ahn, Debsoumya Chakraborti, Kevin Hendrey, Donggyu Kim, and Sang-il Oum, Twin-width of random graphs, Random Structures & Algorithms (2024).
-DOI:10.1002/rsa.21247 / arXiv:2212.07880

Jungho Ahn, Eduard Eiben, O-joung Kwon, and Sang-il Oum, A polynomial kernel for 3-leaf power deletion. Algorithmica (2023).
-DOI:10.1007/s00453-023-01129-9 / arXiv:1911.04249

Jungho Ahn, Kevin Hendrey, Donggyu Kim, and Sang-il Oum, Bounds for the twin-width of graphs. SIAM J. Discrete Math. (2022).
-DOI:10.1137/21M1452834 / arXiv:2110.03957

Jungho Ahn, Lars Jaffke, O-joung Kwon, and Paloma T. Lima. Well-partitioned chordal graphs. Discrete Math. (2022).
-DOI:10.1016/j.disc.2022.112985 / arXiv:2002.10859

Jungho Ahn, Eun Jung Kim, and Euiwoong Lee. Towards constant-factor approximation for chordal/distance-hereditary vertex deletion. Algorithmica (2022).
-DOI:10.1007/s00453-022-00963-7 / arXiv:2009.00809

Refereed Conference Papers

Approximating maximum cut on interval and split graphs beyond Goemans-Williamson
-with Ian DeHaan, Eun Jung Kim, and Euiwoong Lee.
-accepted in APPROX 2025, Aug. 11-13, Berkeley, United States.
-arXiv:2507.10436

Twin-width one
-with Hugo Jacob, Noleen Köhler, Christophe Paul, Amadeus Reinald, and Sebastian Wiederrecht.
-accepted in STACS 2025, Mar. 4-7, Jena, Germany.
-DOI:10.4230/LIPIcs.STACS.2025.6 / arXiv:2501.00991

A coarse Erdős-Pósa theorem
-with Pascal Gollin, Tony Huynh, and O-joung Kwon.
-accepted in SODA25, Jan. 12-15, New Orleans, United States.
-DOI:10.1137/1.9781611978322 / arXiv:2407.05883

Unified almost linear kernels for generalized covering and packing problems on nowhere dense classes
-with Jinha Kim and O-joung Kwon.
-accepted in ISAAC 2023, Dec. 3-6, Kyoto, Japan.
-DOI:10.4230/LIPIcs.ISAAC.2023.5 / arXiv:2207.06660

Three problems on well-partitioned chordal graphs
-with Lars Jaffke, O-joung Kwon, and Paloma T. Lima.
-accepted in CIAC 2021, May 10-12, Larnaca, Cyprus.
-DOI:10.1007/978-3-030-60440-0_12

Towards constant-factor approximation for chordal / distance-hereditary vertex deletion
-with Eun Jung Kim and Euiwoong Lee.
-accepted in ISAAC 2020, Dec. 14-18, Hong Kong.
-DOI:10.4230/LIPIcs.ISAAC.2020.62 / arXiv:2009.00809

A polynomial kernel for 3-leaf power deletion
-with Eduard Eiben, O-joung Kwon, and Sang-il Oum.
-accepted in MFCS 2020, Aug. 24-28, Prague, Czech Republic.
-DOI:10.4230/LIPIcs.MFCS.2020.5 / arXiv:1911.04249

Well-partitioned chordal graphs: obstruction set and disjoint paths
-with Lars Jaffke, O-joung Kwon, and Paloma T. Lima.
-accepted in WG 2020, June 24-26, Leeds, United Kingdom.
-DOI:10.1007/978-3-030-60440-0_12 / arXiv:2002.10859