O-joung Kwon (권오정)

Department of Mathematics
Hanyang University

Graph theory · Combinatorics

Research output

Papers

Selected publications

Journal papers

53. Unavoidable pivot-minors in graphs of large rank-depth (with Jungho Ahn, Kevin Hendrey, and Sang-il Oum)
SIAM Journal on Discrete Mathematics accepted, arXiv:2507.12697

52. Group vertex-arboricity of group-labelled graphs (with Xiaopan Lian)
Discrete Mathematics 349(12) (Dec 2026), 115344, arXiv:2305.01472

51. Pre-assignment problem for unique minimum vertex cover on bounded clique-width graphs
(with Shinwoo An, Yeonsu Chang, Kyungjin Cho, Myounghwan Lee, Eunjin Oh, and Hyeonjun Shin)
Theoretical Computer Sciences 1084 (Sep 20, 2026), 116173, AAAI 2025 arXiv:2408.09591

50. Computing pivot-minors (with Konrad Dabrowski, Francois Dross, Jisu Jeong, Mamadou Kanté, Sang-il Oum, and Daniel Paulusma)
Algorithmica 88:47 (May 20, 2026), WG 2018, arXiv.org:2311.04656

49. Unified almost linear kernels for generalized covering and packing problems on nowhere dense classes (with Jungho Ahn and  Jinha Kim)
Journal of Computer and System Sciences 159 (Aug, 2026) 103782, ISAAC 2023 arXiv:2207.06660

48. Reduced bandwidth: a qualitative strengthening of twin-width in minor-closed classes (and beyond) (with Édouard Bonnet and David Wood)
Journal of Combinatorial Theory Ser. B 178 (May, 2026) pp. 27-66, arXiv:2202.11858

47. On a variant of dichromatic number for digraphs with prescribed sets of arcs (with Xiaopan Lian)
Graphs and combinatorics 42:32 (Mar 4, 2026), arXiv:2307.05897

46. Erdős-Pósa property of A-paths in unoriented group-labelled graphs (with Youngho Yoo)
Combinatorica 46:9 (Mar 4, 2026), arXiv:2411.05372

45. A new width parameter of graphs based on edge cuts: \alpha-edge-crossing width (with Yeonsu Chang and Myounghwan Lee)
Discrete Applied Mathematics 380 (Feb 15, 2026) pp. 492-510, WG 2023 arXiv:2302.04624

44. A unified Erdős-Pósa theorem for cycles in graphs labelled by multiple abelian groups (with J. Pascal Gollin, Kevin Hendrey, Sang-il Oum, and Youngho Yoo)
Mathematische Annalen 393 (Sep 26, 2025) pp 2507-2559, arXiv:2209.09488

43. A half-integral Erdős-Pósa theorem for directed odd cycles (with Ken-ichi Kawarabayashi, Stephan Kreutzer, and Qiqin Xie)
Journal of Combinatorial Theory Ser. B 172 (May, 2025) pp.115-145,  SODA 2023, arXiv:2007.12257

42. A characterization of graphs of radius-r flip-width at most 2 (with Yeonsu Chang, Sejin Ko, and Myounghwan Lee)
Discrete Mathematics 348(4) (Apr, 2025), 114366 arXiv:2306.15206

41. Classes of intersection digraphs with good algorithmic properties (with Lars Jaffke and Jan Arne Telle)
Journal of Graph Theory 106(1) (May, 2024) pp. 110-148, STACS 2022, arXiv:2015.01413

40. On the Erdős-Pósa property of long holes in C4-free graphs (with Tony Huynh)
SIAM Journal on Discrete Mathematics 38(1) (Mar, 2024) pp. 19-42, arXiv:2105.11799

39. A unified half-integral Erdős-Pósa theorem for cycles in graphs labelled by multiple abelian groups (with J. Pascal Gollin, Kevin Hendrey, Ken-ichi Kawarabayashi, and Sang-il Oum)
Journal of the London Mathematical Society 109(1) (Jan, 2024):e12858, arXiv:2102.01986

38. A polynomial kernel for 3-leaf power deletion (with Jungho Ahn, Eduard Eiben, and Sang-il Oum)
Algorithmica 85(10) (May 9th, 2023) pp. 3058–3087, MFCS 2020, arXiv:1911:04249

37. Obstructions for matroids of path-width at most k and graphs of linear rank-width at most k (with Mamadou Kanté, Eun Jung Kim, and Sang-il Oum)
Journal of Combinatorial Theory Ser. B 160 (May, 2023) pp.15-35, STACS 2022, arXiv:2109.12291

36. The grid theorem for vertex-minors (with Jim Geelen, Rose McCarty and Paul Wollan)
Journal of Combinatorial Theory Ser. B 158(1) (Jan, 2023) pp.93-116, arXiv:1909.08113

35. Well-partitioned chordal graphs (with Jungho Ahn, Lars Jaffke, and Paloma T. Lima)
Discrete Mathematics 345(10) (Oct, 2022) 112985, WG 2020 and CIAC 2021, arXiv:2002.10859

34. Rainbow independent sets on dense graph classes (with Jinha Kim and Minki Kim)
Discrete Applied Mathematics 312 (May 15th, 2022) pp.45-51, arXiv:2001.10566

33. Tree pivot-minors and linear rank-width (with Konrad Dabrowski, Francois Dross, Jisu Jeong, Mamadou Kanté, Sang-il Oum, and Daniel Paulusma)
SIAM Journal on Discrete Mathematics 35(4) (Dec 9th, 2021) pp.2922-2945, EUROCOMB 2019, arXiv:2008.00561

32. A system of disjoint representatives of line segments with given k directions (with Jinha Kim and Minki Kim)
Discrete Mathematics 344(12) (Dec 2021), 112621, arXiv:2101.02887

31. Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth (with Eduard Eiben, Robert Ganian and Thekla Hamm)
Journal of Computer and System Sciences. 121 (Nov, 2021), pp 57-75, MFCS 2019, arXiv:1908.10132

30. A polynomial kernel for Distance-Hereditary Vertex Deletion (with Eun Jung Kim)
Algorithmica 83(7) (July, 2021), pp. 2096-2141, WADS 2017, arXiv:1610.07229

29. Obstructions for bounded shrub-depth and rank-depth (with Rose McCarty, Sang-il Oum, and Paul Wollan)
Journal of Combinatorial Theory Ser. B. 149 (Jul, 2021), pp 76-91  arXiv:1911.00230

28. A Menger-like property of tree-cut width (with Archontia Giannopoulou, Jean-Florent Raymond, and Dimitrios M. Thilikos)
Journal of Combinatorial Theory Ser. B. 148 (May, 2021), pp 1-22, arXiv:1808.00863

27. Packing and covering induced subdivisions (with Jean-Florent Raymond)
SIAM Journal on Discrete Mathematics 35(2) (Apr 7, 2021), pp 597-636, arXiv:1803.07581

26. Graphs of bounded depth-2 rank-brittleness (with Sang-il Oum)
Journal of Graph Theory. 96(3) (Mar, 2021), pp 361-378, arXiv:1906.05753

25. Branch-depth: Generalizing tree-depth of graphs (with Matt DeVos and Sang-il Oum)
European Journal of Combinatorics. 90 (Dec, 2020), 103186, arXiv:1903.11988

24. Erdős-Pósa property of chordless cycles and its applications (with Eun Jung Kim)
Journal of Combinatorial Theory Ser. B. 145 (Nov, 2020), pp 65-112, (SODA 2018, arXiv:1711:00667, Movie from Discrete Seminar at KAIST )

23. Graphs without two vertex-disjoint S-cycles (with Minjeong Kang and Myounghwan Lee)
Discrete Mathematics. 343(10) (Oct 2020) 111997. (arXiv:1908.09065)

22. An optimal XP algorithm for Hamiltonian cycle on graphs of bounded clique-width (with Benjamin Bergougnoux and Mamadou Kanté)
Algorithmica. 82(6) (June, 2020), pp 1654-1674, WADS 2017, arXiv:1702.06095

21. Mim-width I. Induced path problems (with Lars Jaffke and Jan Arne Telle)
Discrete Applied Mathematics. 278 (May 15, 2020), pp 153-168, IPEC 2017, arXiv:1708:04536

20. Scattered classes of graphs (with Sang-il Oum)
SIAM Journal on Discrete Mathematics 34(1) (Mar 31. 2020), pp 972–999, arXiv:1801.06004

19. Mim-width II. The feedback vertex set problem (with Lars Jaffke and Jan Arne Telle)
Algorithmica. 82(1). (Jan, 2020), pp 118-145, STACS 2018, arXiv:1710.07148

18. On low rank-width colorings (with Michal Pilipczuk and Sebastian Siebertz)
European Journal of Combinatorics. 83. (Jan, 2020), WG 2017, arXiv:1703.03304

17. Classes of graphs with no long cycle as a vertex-minor are polynomially chi-bounded (with Ringi Kim, Sang-il Oum, and Vaidy Sivaraman)
Journal of Combinatorial Theory Ser. B. 140 (Jan. 2020), pp 372-386, arXiv:1809.04278

16. Mim-Width III. Graph Powers and Generalized Distance Domination Problems (with Lars Jaffke, Torstein Stromme, and Jan Arne Telle)
Theoretical Computer Sciences. 796. (Dec, 2019) pp 216-236, IPEC 2018, arXiv:1803.03514

15. Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms (with Édouard Bonnet, Nick Brettell, and Dániel Marx)
Algorithmica. 81(10) (Oct 2019), pp 3890-3935, IPEC 2017, arXiv:1704.06757, Movie from Discrete Seminar at KAIST 

14. Chi-boundedness of graph classes excluding wheel vertex-minors (with Hojin Choi,  Sang-il Oum and Paul Wollan)
Journal of Combinatorial Theory Ser. B. 135 (Mar. 2019), pp 319-348, arXiv:1702.07851, Movie from SigMa 2017

13. Linear rank-width of distance-hereditary graphs II. Vertex-minor obstructions (with Mamadou Kanté)
European Journal of Combinatorics. 74 (Dec. 2018), pp 110-139, arXiv:1508.04718

12. A single-exponential fixed-parameter algorithm for Distance-Hereditary Vertex Deletion (with Eduard Eiben and Robert Ganian)
Journal of Computer and System Sciences. 97 (Nov. 2018), pp 121-146, arXiv:1604:06056

11. A width parameter useful for chordal and co-comparability graphs (with Dong Yeup Kang, Torstein Stromme, and Jan Arne Telle)
Theoretical Computer Sci. 704 (15. Dec. 2017), pp 1-17 , WALCOM 2017

10. Packing and covering immersion models of planar subcubic graphs (with Archontia Giannopoulou, Jean-Florent Raymond, and Dimitrios M. Thilikos)
European. J. Combin. 65 (Oct. 2017), pp 154-167 , WG 2016

9. A polynomial kernel for Block Graph Deletion (with Eun Jung Kim)
Algorithmica. 79 (Sep, 2017), pp 251-270 , IPEC 2015

8. An FPT algorithm and a polynomial kernel for Linear Rankwidth-1 Vertex Deletion (with Mamadou Kanté, Eun Jung Kim, and Christophe Paul)
Algorithmica. 79 (Sep, 2017), pp 66-95 , IPEC 2015

7. Linear rank-width of distance-hereditary graphs I. A polynomial time algorithm (with Isolde Adler and Mamadou Kanté)
Algorithmica. 78 (May, 2017), pp 342-377 , WG 2014

6. Coloring graphs without fan vertex-minors and graphs without cycle pivot-minors (with Ilkyoo Choi and Sang-il Oum)
Journal of Combinatorial Theory Ser. B. 123 (March, 2017), pp. 126-147

5. Characterizing width two for variants of treewidth (with Hans L. Bodlaender, Stefan Kratsch, Vincent Kreuzen, and Seongmin Ok)
Discrete Applied Math. 216(Jan 10, 2017), pp. 29-46

4. Tree-depth and vertex-minors (with Pétr Hlineny, Jan Obdrzalek, and Sebastian Ordyniak)
European J. Combin. 56 (Augest, 2016), pp. 46-56

3. Excluded vertex-minors for graphs of linear rank-width at most k (with Jisu Jeong and Sang-il Oum)
European J. Combin. 41(October, 2014), pp. 242-257  , STACS 2013

2. Unavoidable vertex-minors in large prime graphs (with Sang-il Oum)
European J. Combin. 41(October, 2014), pp. 100-127

1. Graphs of small rank-width are pivot-minors of graphs of small tree-width (with Sang-il Oum)
Discrete Applied Math. 168(May 11, 2014), pp. 108-118

Refereed conference papers without journal version

11. An FPT algorithm for cycle rank on semi-complete digraphs (with Seokbeom Kim and Myounghwan Lee)
ISAAC 2026 arXiv:2606.29336

10. Moderately beyond clique-width: reduced component max-leaf and related parameter
(with Édouard Bonnet, Yeonsu Chang, Julien Duron, and Colin Geniet)
ESA 2026 arXiv:2604.19138

9. The Erdős-Pósa property for circle graphs as vertex-minors (with Rutger Campbell, J. Pascal Gollin, Meike Hatzel, Rose McCarty,  Sang-il Oum, and Sebastian Wiederrecht)
SODA 2026 arxiv:2506.03973

8. A coarse Erdős-Pósa theorem (with Jungho Ahn,  J. Pascal Gollin, and Tony Huynh)
SODA 2025 arXiv:2407.05883

7.  A unifying framework for characterizing and computing width measures (with Eduard Eiben, Robert Ganian, Thekla Hamm, Lars Jaffke)
ITCS 2022 arXiv:2109.14610

6. Directed tangle-tree decomposition and its applications (with Archontia Giannopoulou, Ken-ichi Kawarabayashi, and Stephan Kreutzer)
SODA 2022 arXiv:2009.13184

5. Close relatives of Feedback Vertex Set without single-exponential algorithms parameterized by treewidth (with Benjamin Bergougnoux, Édouard Bonnet, and Nick Brettell)
IPEC 2020 arXiv:2007.14179

4. The Directed Flat Wall Theorem (with Archontia Giannopoulou, Ken-ichi Kawarabayashi, and Stephan Kreutzer)
SODA 2020

3. Lean tree-cut decompositions: obstructions and algorithms (with Archontia Giannopoulou, Jean-Florent Raymond, and Dimitrios M. Thilikos)
STACS 2019 (arXiv:1808.00863)

2. Neighborhood complexity and kernelization for nowhere dense classes of graphs (with Kord Eickmeyer, Archontia Giannopoulou, Stephan Kreutzer, Michal Pilipczuk, Roman Rabinovich, and Sebastian Siebertz)
ICALP 2017 (full version : arXiv:1612.08197)

1. Parameterized vertex deletion problems for hereditary graph classes with a block property (with Édouard Bonnet, Nick Brettell, and Dániel Marx)
WG 2016 (full version : arXiv:1603.05945)

Submitted

3. Erdős-Pósa property for induced packings of long S-cycles (with Jungho Ahn)
arXiv:2608.22349 submitted

2. Unavoidable butterfly minors in digraphs of large cycle rank (with Meike Hatzel, Myounghwan Lee, and Sebastian Wiederrecht)
arXiv:2507.11814 submitted

1. Treewidth versus clique number. IV. Tree-independence number of graphs excluding an induced star
(with Clément Dallard, Matjaž Krnc, Martin Milanič, Andrea Munaro, Kenny Štorgel, and Sebastian Wiederrecht)
arXiv:2402.11222 submitted

Thesis

Ph.D. Thesis On the structural and algorithmic properties of linear rank-width [File]
Master Thesis Connecting rank-width and tree-width via pivot-minors [File]

Manuscript

A new family of hypohamiltonian graphs generalizing Lindgren’s construction (with Taesung Kim) file

Erdos-Posa property of minor-models with prescribed vertex sets (with Dániel Marx) arXiv:1904.00879 manuscript