Current Position and Address

Assistant professor
Department of Mathematics, Incheon National University (인천대학교).
119 Academy-ro, Songdo 1(il)-dong, Yeonsu-gu, Incheon, South Korea.

Email: ojoungkwon (at), ojoungkwon (at) (please email to here for subjects in INU)
CV: [PDF] (updated in Mar. 2019)

Currently, I am receiving a grant of 200 million won (approx 160,000 Euro) for 2018-2022, by the National Research Foundation of Korea. The title is ‘Tight polynomial kernelizations for various graph modification problems”. If you want to visit me, I would like to support you.

Research Interests

Graph theory, Combinatorial Optimization, Structural Graph Theory, Parameterized Complexity.

I am interested in various structural aspects of graphs. Tree-width and rank-width are graph width parameters that I have been mainly working on. Especially generalizing well-developed theory on tree-width and graph minor operation to rank-width and vertex-minor operation is one of main projects. Our community conjectured that for every circle graph H, there is a large constant c_H such that every graph of rank-width at least c_H must contain H as a vertex-minor. The other interesting conjecture is Geelen’s conjecture that for every graph H, the class of graphs having no H vertex-minor is chi-bounded. We are still very far from completely understanding about these conjectures, and I am trying to extend knowledge about these conjectures. Recently I am working a lot on mim-width parameter, which is relatively new, and generalizes tree-width and rank-width.

Parameterized complexity and multivariate algorithmics are other main area of my research. Different from classical analysis on algorithms, in this area, we are interested in analyzing with additional parameters. For instance, the problem of seeking a vertex cover of size at most k is an NP-hard problem, but it can be solved in time 2^{O(k)}poly(n). If an algorithm with running time f(k)poly(n) exists, then we say that the problem is fixed parameter tractable with respect to the parameter k. There are lots of interesting open problems in this area about determining some problem is fixed parameter tractable or not, or for some fixed parameter tractable problem, finding an optimal running with respect to the function of parameter k. Especially obtaining a polynomial kernelization algorithm is quite related to structural graph theory, and in this connection, I am interested in designing kernelization algorithms on various graph modification problems. One of big problems in the area is to know whether Interval Vertex Deletion admits a polynomial kernel or not. We have a very strong community; see wiki homepage for looking at news, new papers, and newly announced jobs.

I am also interested in working on pure graph theory; for instance, induced subdivision, Erdös-Pósa property, graph coloring, and sparsity (bounded expansion and nowhere dense graph classes).

FPT news Feb. 2018 : Here is a news paper of fpt community that contains a short article about my recent SODA 2018 paper ‘Erdos-Posa property of chordless cycles and its applications’.


I am one of the members organizing Incheon Combinatorics Seminar. We organize meetings in Thursday (Incheon National University, Inha University) or Friday (SUNY Korea) for this spring semester. We are happy to invite you to give a talk. Please e-mail me if you are interested in.


Rose McCarty will visit INU (tentative plan : 24 Apr – 4 May, 2019)
Lars Jaffke will visit INU (tentative plan : 13 – 24 May, 2019)
Workshop on Kernelization 2019 in Bergen (3-7, June, 2019)
2019 Combinatorics Workshop (organized at Incheon, 13-15, Aug, 2019)
Graph Colouring: from Structure to Algorithms (June 30-July 5, 2019)

Previous Positions

Technische Universität Berlin

Berlin, Germany (Jul. 2016 – Feb. 2018)
Postdoctor in Institut fur Softwaretechnik und Theoretische Informatik
Advisor: Stephan Kreutzer



Hungarian Academy of Sciences

Budapest, Hungary (Jul. 2015 – Jun. 2016)
Researcher in Institute for Computer Science and Control (MTA SZTAKI)
Advisor: Dániel Marx


Ph.D. in Mathematical Sciences, KAIST (2012-2015)
Advisor : Prof. Sang-il Oum
M.S. in Mathematical Sciences, KAIST (2010-2012)
B.S. in Mathematics, Hanyang University (2003-2010)


RWTH Aachen University Research Fellowship Korea, Jan – Mar, 2015
KIAS Fellowship for Seoul ICM 2014
SIAM Student Travel Award – SIAM Conference on Discrete Mathematics, June, 2014
Travel Grants for graduate students and young researchers – 14th Max Planck Advanced Course on the Foundations of Computer Science, Aug, 2013

Research Visits

National Institute of Informatics, Tokyo, Japan. Hosted by Dr. Kawarabayashi (23. Jul. 2018 ~ 28. Jul. 2018)
University of Bari, Italy. Hosted by Prof. Paul Wollan (13. Nov. 2017 ~ 17. Nov. 2017)
University of Waterloo, Canada. Hosted by Dr. Ringi Kim (24. Jul. 2017 ~ 28. Jul. 2017)
University of Lyon, France. Hosted by Dr. Valia Mitsou (3. Apr. 2017 ~ 7. Apr. 2017)
Universidad Politecnica de Valencia, Spain. Hosted by Prof. Jan Arne Telle (27. Mar. 2017 ~ 1. Apr. 2017)
Durham University, UK. Hosted by Prof. Daniel Paulusma (27. Feb. 2017 ~ 3. Mar. 2017)
University of Warsaw, Poland. Hosted by Prof. Marcin Pilipczuk (11. Jan. 2017 ~ 13. Jan. 2017)
KAIST, South Korea. Hosted by Prof. Sang-il Oum (20. Nov. 2016 ~ 10. Nov. 2016)
Universite Blaise Pascal, France. Hosted by Prof. Mamadou Kanté (7. Nov. 2016 ~ 12. Nov. 2016)
University of Bergen, Norway. Hosted by Prof. Jan Arne Telle (22. May. 2016 ~ 28. May. 2016)
TU Wien, Austria. Hosted by Dr. Robert Ganian (14. Mar. 2016 ~ 18. Mar. 2016)
Masaryk University, Czech. Hosted by Prof. Petr Hlineny (16. Nov. 2015 ~ 20. Nov. 2015)
MTA SZTAKI, Hungary. Hosted by Dr. Dániel Marx (22. Mar, 2015 ~ 28. Mar, 2015)
DTU, Denmark. Hosted by Dr. Seongmin Ok (23. Feb, 2015 ~ 27. Feb, 2015)
Bonn University, Germany. Hosted by Prof. Stefan Kratsch (16. Feb, 2015 ~ 18. Feb, 2015)
LIRMM in Montpellier, France. Hosted by Prof. Christophe Paul (26. Jan, 2015 ~ 30. Jan, 2015)
RWTH Aachen University, Germany. Hosted by Prof. Peter Rossmanith (6. Jan, 2015 ~ 31. Mar, 2015)
Universite Blaise Pascal, France. Hosted by Prof. Mamadou Kanté (7. July. 2014 ~ 22. July. 2014)
Utrecht University, Netherlands. Hosted by Prof. Hans Bodlaender (15. Feb. 2014 ~ 7. Mar. 2014)
Universite Blaise Pascal, France. Hosted by Prof. Mamadou Kanté (8. July. 2013 ~ 21. July. 2013)
Masaryk University, Czech. Hosted by Prof. Petr Hlineny (19. May. 2013 ~ 24. May. 2013)
University of Hamburg, Germany. Hosted by Prof. Reinhard Diestel (13. Feb. 2013 ~ 31. Aug. 2013)


Lars Jaffke 13-24, May, 2019
Rose McCarty 22, Apr-3, May, 2019
Tony Huynh 3-16, Dec, 2018
Eduard Eiben 7-19, Oct, 2018
Benjamin Bergougnoux 6-14, Oct, 2018


Co-organizing 2019 Combinatorics Workshop