Jungho Ahn
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Research Interests
Jungho Ahn has a total of 19 co-authors. Here are the top co-authors by number of shared publications:
- Sang-Il Oum
Discrete Mathematics Group Institute for Basic Science (IBS) Daejeon South Korea
6 shared publications - O-Joung Kwon
Department of Mathematics, Hanyang University, Seoul, South Korea
5 shared publications - Lars Jaffke
NHH Norwegian School of Economics, Bergen, Norway
3 shared publications - Eduard Eiben
Royal Holloway, University of London
2 shared publications Kevin Hendrey
School of Mathematics, Monash University, Melbourne, Australia
2 shared publicationsPaloma T. Lima
University of Bergen
2 shared publications
Latest Publications
- 3 February 2026
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 159
Unified almost linear kernels for generalized covering and packing problems on nowhere dense classes
- 3 February 2026
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 159
Unified almost linear kernels for generalized covering and packing problems on nowhere dense classes
- Top Cited Papers
- 2 July 2025
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 377, 10-17
The proper conflict-free -coloring problem and the odd -coloring problem are NP-complete on bipartite graphs- 2 July 2025
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 377, 10-17
Top Cited PapersThe proper conflict-free -coloring problem and the odd -coloring problem are NP-complete on bipartite graphs - 21 April 2025
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 39 (2) , 783-833
Twin-Width of Subdivisions of Multigraphs
For each [Formula: see text], we construct a finite set [Formula: see text] of multigraphs such that for each graph [Formula: see text] of girth at least 5 obtained from a multigraph [Formula: see text] by subdividing each edge at least two times, [Formula: see text] has twin-width at most [Formula: see text] if and only if [Formula: see text] has no minor in [Formula: see text]. This answers a question of Bergé, Bonnet, and Déprés asking for the structure of graphs [Formula: see text] such that each long subdivision of [Formula: see text] has twin-width 4. As a corollary, we show that the [Formula: see text] grid has twin-width 4, which answers a question of Schidler and Szeider.
- 21 April 2025
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 39 (2) , 783-833
Twin-Width of Subdivisions of Multigraphs
For each [Formula: see text], we construct a finite set [Formula: see text] of multigraphs such that for each graph [Formula: see text] of girth at least 5 obtained from a multigraph [Formula: see text] by subdividing each edge at least two times, [Formula: see text] has twin-width at most [Formula: see text] if and only if [Formula: see text] has no minor in [Formula: see text]. This answers a question of Bergé, Bonnet, and Déprés asking for the structure of graphs [Formula: see text] such that each long subdivision of [Formula: see text] has twin-width 4. As a corollary, we show that the [Formula: see text] grid has twin-width 4, which answers a question of Schidler and Szeider.
- 14 June 2024
- Published by Wiley in Random Structures & Algorithms
- Vol. 65 (4) , 794-831
Twin‐width of random graphs
We investigate the twin‐width of the Erdős‐Rényi random graph . We unveil a surprising behavior of this parameter by showing the existence of a constant such that with high probability, when , the twin‐width is asymptotically , whereas, when or , the twin‐width is significantly higher than . In addition, we show that the twin‐width of is concentrated around within an interval of length . For the sparse random graph, we show that with high probability, the twin‐width of is when .
- 14 June 2024
- Published by Wiley in Random Structures & Algorithms
- Vol. 65 (4) , 794-831
Twin‐width of random graphs
We investigate the twin‐width of the Erdős‐Rényi random graph . We unveil a surprising behavior of this parameter by showing the existence of a constant such that with high probability, when , the twin‐width is asymptotically , whereas, when or , the twin‐width is significantly higher than . In addition, we show that the twin‐width of is concentrated around within an interval of length . For the sparse random graph, we show that with high probability, the twin‐width of is when .
- Open Access
A polynomial kernel for $3$-leaf power deletion
For a non-negative integer $\ell$, the $\ell$-leaf power of a tree $T$ is a simple graph $G$ on the leaves of $T$ such that two vertices are adjacent in $G$ if and only if their distance in $T$ is at most $\ell$. We provide a polynomial kernel for the problem of deciding whether we can delete at most $k$ vertices to make an input graph a $3$-leaf power of some tree. More specifically, we present a polynomial-time algorithm for an input instance $(G,k)$ for the problem to output an equivalent instance $(G',k')$ such that $k'\leq k$ and $G'$ has at most $O(k^{14})$ vertices.Open AccessA polynomial kernel for $3$-leaf power deletion
For a non-negative integer $\ell$, the $\ell$-leaf power of a tree $T$ is a simple graph $G$ on the leaves of $T$ such that two vertices are adjacent in $G$ if and only if their distance in $T$ is at most $\ell$. We provide a polynomial kernel for the problem of deciding whether we can delete at most $k$ vertices to make an input graph a $3$-leaf power of some tree. More specifically, we present a polynomial-time algorithm for an input instance $(G,k)$ for the problem to output an equivalent instance $(G',k')$ such that $k'\leq k$ and $G'$ has at most $O(k^{14})$ vertices. - 9 May 2023
- Published by Springer Nature in Algorithmica
- Vol. 85 (10) , 3058-3087
A Polynomial Kernel for 3-Leaf Power Deletion
- 9 May 2023
- Published by Springer Nature in Algorithmica
- Vol. 85 (10) , 3058-3087
A Polynomial Kernel for 3-Leaf Power Deletion
- Open Access
Bounds for the Twin-width of Graphs
Bonnet, Kim, Thomass\'{e}, and Watrigant (2020) introduced the twin-width of a graph. We show that the twin-width of an $n$-vertex graph is less than $(n+\sqrt{n\ln n}+\sqrt{n}+2\ln n)/2$, and the twin-width of an $m$-edge graph for a positive $m$ is less than $\sqrt{3m}+ m^{1/4} \sqrt{\ln m} / (4\cdot 3^{1/4}) + 3m^{1/4} / 2$. Conference graphs of order $n$ (when such graphs exist) have twin-width at least $(n-1)/2$, and we show that Paley graphs achieve this lower bound. We also show that the twin-width of the Erd\H{o}s-R\'{e}nyi random graph $G(n,p)$ with $1/n\leq p=p(n)\leq 1/2$ is larger than $2p(1-p)n - (2\sqrt{2}+\varepsilon)\sqrt{p(1-p)n\ln n}$ asymptotically almost surely for any positive $\varepsilon$. Lastly, we calculate the twin-width of random graphs $G(n,p)$ with $p\leq c/n$ for a constant $c<1$, determining the thresholds at which the twin-width jumps from $0$ to $1$ and from $1$ to $2$.Open AccessBounds for the Twin-width of Graphs
Bonnet, Kim, Thomass\'{e}, and Watrigant (2020) introduced the twin-width of a graph. We show that the twin-width of an $n$-vertex graph is less than $(n+\sqrt{n\ln n}+\sqrt{n}+2\ln n)/2$, and the twin-width of an $m$-edge graph for a positive $m$ is less than $\sqrt{3m}+ m^{1/4} \sqrt{\ln m} / (4\cdot 3^{1/4}) + 3m^{1/4} / 2$. Conference graphs of order $n$ (when such graphs exist) have twin-width at least $(n-1)/2$, and we show that Paley graphs achieve this lower bound. We also show that the twin-width of the Erd\H{o}s-R\'{e}nyi random graph $G(n,p)$ with $1/n\leq p=p(n)\leq 1/2$ is larger than $2p(1-p)n - (2\sqrt{2}+\varepsilon)\sqrt{p(1-p)n\ln n}$ asymptotically almost surely for any positive $\varepsilon$. Lastly, we calculate the twin-width of random graphs $G(n,p)$ with $p\leq c/n$ for a constant $c<1$, determining the thresholds at which the twin-width jumps from $0$ to $1$ and from $1$ to $2$. - 5 April 2022
- Published by Springer Nature in Algorithmica
- Vol. 84 (7) , 2106-2133
Towards Constant-Factor Approximation for Chordal/Distance-Hereditary Vertex Deletion
- 5 April 2022
- Published by Springer Nature in Algorithmica
- Vol. 84 (7) , 2106-2133
Towards Constant-Factor Approximation for Chordal/Distance-Hereditary Vertex Deletion
- 30 November 2020
- Published by The International Academic Forum of Korean Language and Literature in Journal of Korean Culture
- Vol. 51, 79-117
A Study on Developing Evaluation Standard for Korean Language Textbooks: Focusing on domestic and ESL/EFL case studies
본고는 국내외의 교재 · 교과서의 평가 기준 설정 사례를 분석하고, 분석의 결과로 도출된 시사점을 반영하여 한국어 교재의 평가 기준을 마련하는 것을 목적으로 한다. 국내 사례의 경우, 한국어 교재의 평가 혹은 분석 기준 설정에 관한 선행 연구를 고찰하고, 교육부의 교과용도서 개발을 위한 편찬상의 유의점 및 검정 기준, 국립국어원의 한국어 교재 추천 제도 등에서 제시된 교재 평가 기준과 관련된 항목들을 분석하였다. 더불어 외국어로서의 언어 교육용 교재의 평가 기준에 보다 집중하고자 ESL/EFL 교재의 평가 기준 설정에 대한 해외 사례도 분석하였다. 본고는 이렇게 한국의 교과용도서 평가 기준, 기존의 한국어 교재 평가 기준, 해외의 영어 교재 평가 기준을 분석하여 종합적이고 체계적인 평가 기준의 체계를 마련하였으며, 크게는 범령 규범 및 공정성’, ‘외형 및 실용성’, ‘교육과정의 준수’, ‘교육 방법 및 내용’의 4대 대범주를 설정하고 각각의 하위 평가 기준을 제시하였다. 또 범령 규범 및 공정성’ 범주에 10개, ‘외형 및 실용성’ 범주에 20개, ‘교육과정의 준수’ 범주에 7개, ‘교육 방법 및 내용’ 범주에 교육 방법 8개, 교육 내용 65개 범주로 73개 항목을 제시, 총 110개의 항목을 제시하여 구체적이고 포괄적인 평가 기준을 개발하고자 하였다.
- 30 November 2020
- Published by The International Academic Forum of Korean Language and Literature in Journal of Korean Culture
- Vol. 51, 79-117
A Study on Developing Evaluation Standard for Korean Language Textbooks: Focusing on domestic and ESL/EFL case studies
본고는 국내외의 교재 · 교과서의 평가 기준 설정 사례를 분석하고, 분석의 결과로 도출된 시사점을 반영하여 한국어 교재의 평가 기준을 마련하는 것을 목적으로 한다. 국내 사례의 경우, 한국어 교재의 평가 혹은 분석 기준 설정에 관한 선행 연구를 고찰하고, 교육부의 교과용도서 개발을 위한 편찬상의 유의점 및 검정 기준, 국립국어원의 한국어 교재 추천 제도 등에서 제시된 교재 평가 기준과 관련된 항목들을 분석하였다. 더불어 외국어로서의 언어 교육용 교재의 평가 기준에 보다 집중하고자 ESL/EFL 교재의 평가 기준 설정에 대한 해외 사례도 분석하였다. 본고는 이렇게 한국의 교과용도서 평가 기준, 기존의 한국어 교재 평가 기준, 해외의 영어 교재 평가 기준을 분석하여 종합적이고 체계적인 평가 기준의 체계를 마련하였으며, 크게는 범령 규범 및 공정성’, ‘외형 및 실용성’, ‘교육과정의 준수’, ‘교육 방법 및 내용’의 4대 대범주를 설정하고 각각의 하위 평가 기준을 제시하였다. 또 범령 규범 및 공정성’ 범주에 10개, ‘외형 및 실용성’ 범주에 20개, ‘교육과정의 준수’ 범주에 7개, ‘교육 방법 및 내용’ 범주에 교육 방법 8개, 교육 내용 65개 범주로 73개 항목을 제시, 총 110개의 항목을 제시하여 구체적이고 포괄적인 평가 기준을 개발하고자 하였다.