Sang-Il Oum
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
Sang-Il Oum has a total of 136 co-authors. Here are the top co-authors by number of shared publications:
- O-Joung Kwon
Department of Mathematics, Hanyang University, Seoul, South Korea
27 shared publications - Jisu Jeong
Clova AI Research NAVER Corp Seongnam Korea
12 shared publications - Eun Jung Kim
Korea Advanced Institute of Science & Technology, Daejeon, South Korea
8 shared publications - Donggyu Kim
Discrete Mathematics Group Institute for Basic Science (IBS) Daejeon South Korea
6 shared publications - Jungho Ahn
Discrete Mathematics Group Institute for Basic Science (IBS) Daejeon South Korea
6 shared publications - Mamadou Moustapha Kanté
Université Clermont Auvergne, Clermont Auvergne INP, LIMOS, CNRS, Clermont-Ferrand, France
6 shared publications
Latest Publications
- 20 May 2026
- Published by Springer Nature in Algorithmica
- Vol. 88 (3) , 47
Computing Pivot-Minors
- Open Access
Blind cop-width and balanced minors of graphs
We investigate a pursuit-evasion game on an undirected graph in which a robber, moving at a fixed constant speed, attempts to evade a team of cops who are blind to the robber's location and can quickly travel between any pair of vertices in the graph. The blind cop-width is the minimum number of cops needed to catch the robber on a given graph. We link it with other known graph parameters defined in terms of pursuit-evasion games, and show a new lower bound with respect to treewidth. The proof introduces the notion of balanced minors, where all branch sets of a minor model have equal size.
Open AccessBlind cop-width and balanced minors of graphs
We investigate a pursuit-evasion game on an undirected graph in which a robber, moving at a fixed constant speed, attempts to evade a team of cops who are blind to the robber's location and can quickly travel between any pair of vertices in the graph. The blind cop-width is the minimum number of cops needed to catch the robber on a given graph. We link it with other known graph parameters defined in terms of pursuit-evasion games, and show a new lower bound with respect to treewidth. The proof introduces the notion of balanced minors, where all branch sets of a minor model have equal size.
- Open Access
- 26 September 2025
- Published by Springer Nature in Mathematische Annalen
- Vol. 393 (2) , 2507-2559
A unified Erdős–Pósa theorem for cycles in graphs labelled by multiple abelian groups
In 1965, Erdős and Pósa proved that there is an (approximate) duality between the maximum size of a packing of cycles and the minimum size of a vertex set hitting all cycles. Such a duality does not hold for odd cycles, and Dejter and Neumann-Lara asked in 1988 to find all pairs $${(\ell , z)}$$ of integers where such a duality holds for the family of cycles of length $$\ell $$ modulo z . We characterise all such pairs, and we further generalise this characterisation to cycles in graphs labelled with a bounded number of abelian groups, whose values avoid a bounded number of elements of each group. This unifies almost all known types of cycles that admit such a duality, and it also provides new results. Moreover, we characterise the obstructions to such a duality in this setting, and thereby obtain an analogous characterisation for cycles in graphs embeddable on a fixed compact orientable surface.- 26 September 2025
- Published by Springer Nature in Mathematische Annalen
- Vol. 393 (2) , 2507-2559
Open AccessA unified Erdős–Pósa theorem for cycles in graphs labelled by multiple abelian groups
In 1965, Erdős and Pósa proved that there is an (approximate) duality between the maximum size of a packing of cycles and the minimum size of a vertex set hitting all cycles. Such a duality does not hold for odd cycles, and Dejter and Neumann-Lara asked in 1988 to find all pairs $${(\ell , z)}$$ of integers where such a duality holds for the family of cycles of length $$\ell $$ modulo z . We characterise all such pairs, and we further generalise this characterisation to cycles in graphs labelled with a bounded number of abelian groups, whose values avoid a bounded number of elements of each group. This unifies almost all known types of cycles that admit such a duality, and it also provides new results. Moreover, we characterise the obstructions to such a duality in this setting, and thereby obtain an analogous characterisation for cycles in graphs embeddable on a fixed compact orientable surface. - Open Access
- 28 August 2025
- Published by Elsevier in Journal of Combinatorial Theory, Series B
- Vol. 176, 30-73
Reuniting χ-boundedness with polynomial χ-boundedness
- 28 August 2025
- Published by Elsevier in Journal of Combinatorial Theory, Series B
- Vol. 176, 30-73
Open AccessReuniting χ-boundedness with polynomial χ-boundedness
- Open Access
Unavoidable pivot-minors in graphs of large rank-depth
Shrub-depth and rank-depth are related graph parameters that are dense analogs of tree-depth. We prove that for every positive integer $t$, every graph of sufficiently large rank-depth contains a pivot-minor isomorphic to a path on $t$ vertices or a graph consisting of two disjoint cliques of size $t$ joined by a half graph. This answers an open problem raised by Kwon, McCarty, Oum, and Wollan in 2021.Open AccessUnavoidable pivot-minors in graphs of large rank-depth
Shrub-depth and rank-depth are related graph parameters that are dense analogs of tree-depth. We prove that for every positive integer $t$, every graph of sufficiently large rank-depth contains a pivot-minor isomorphic to a path on $t$ vertices or a graph consisting of two disjoint cliques of size $t$ joined by a half graph. This answers an open problem raised by Kwon, McCarty, Oum, and Wollan in 2021. - 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 - Open Access
The Erdős-Pósa property for circle graphs as vertex-minors
We prove that for any circle graph $H$ with at least one edge and for any positive integer $k$, there exists an integer $t=t(k,H)$ so that every graph $G$ either has a vertex-minor isomorphic to the disjoint union of $k$ copies of $H$, or has a $t$-perturbation with no vertex-minor isomorphic to $H$. Using the same techniques, we also prove that for any planar multigraph $H$, every binary matroid either has a minor isomorphic to the cycle matroid of $kH$, or is a low-rank perturbation of a binary matroid with no minor isomorphic to the cycle matroid of $H$.Open AccessThe Erdős-Pósa property for circle graphs as vertex-minors
We prove that for any circle graph $H$ with at least one edge and for any positive integer $k$, there exists an integer $t=t(k,H)$ so that every graph $G$ either has a vertex-minor isomorphic to the disjoint union of $k$ copies of $H$, or has a $t$-perturbation with no vertex-minor isomorphic to $H$. Using the same techniques, we also prove that for any planar multigraph $H$, every binary matroid either has a minor isomorphic to the cycle matroid of $kH$, or is a low-rank perturbation of a binary matroid with no minor isomorphic to the cycle matroid of $H$. - 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.
- Open Access
- 20 March 2025
- Published by Wiley in Journal of Graph Theory
- Vol. 109 (4) , 446-453
Note on Hamiltonicity of Basis Graphs of Even Delta‐Matroids
We show that the basis graph of an even delta‐matroid is Hamiltonian if it has more than two vertices. More strongly, we prove that for two distinct edges and sharing a common end, it has a Hamiltonian cycle using and avoiding unless it has at most two vertices or it is a cycle of length at most four. We also prove that if the basis graph is not a hypercube graph, then each vertex belongs to cycles of every length , and each edge belongs to cycles of every length . For the last theorem, we provide two proofs, one of which uses the result of Naddef (1984) on polytopes and the result of Chepoi (2007) on basis graphs of even delta‐matroids, and the other is a direct proof using various properties of even delta‐matroids. Our theorems generalize the analogous results for matroids by Holzmann and Harary (1972) and Bondy and Ingleton (1976).
- 20 March 2025
- Published by Wiley in Journal of Graph Theory
- Vol. 109 (4) , 446-453
Open AccessNote on Hamiltonicity of Basis Graphs of Even Delta‐Matroids
We show that the basis graph of an even delta‐matroid is Hamiltonian if it has more than two vertices. More strongly, we prove that for two distinct edges and sharing a common end, it has a Hamiltonian cycle using and avoiding unless it has at most two vertices or it is a cycle of length at most four. We also prove that if the basis graph is not a hypercube graph, then each vertex belongs to cycles of every length , and each edge belongs to cycles of every length . For the last theorem, we provide two proofs, one of which uses the result of Naddef (1984) on polytopes and the result of Chepoi (2007) on basis graphs of even delta‐matroids, and the other is a direct proof using various properties of even delta‐matroids. Our theorems generalize the analogous results for matroids by Holzmann and Harary (1972) and Bondy and Ingleton (1976).