Sang-il Oum

activity

20092026

most citedRank-width: Algorithmic and structural results

47 citations · 678 across the 85 of their papers we have counts for

collaborators

88 papers

math.CO2026

Every tournament of dichromatic number $10 k^{2}$ has a vertex whose out-neighborhood has dichromatic number more than $k$

Seokbeom Kim, Sang-il Oum

The dichromatic number of a tournament is the minimum number of colors needed to color the vertices so that no directed cycle is monochromatic. Nguyen, Scott, and Seymour (2025) as…

math.CO2026

A double-logarithmic upper bound on the chromatic number of the associahedron

Sang-il Oum, David R. Wood

We show that the associahedron $A_{n}$ has chromatic number $O (lo g lo g n)$ , improving on the previously best known upper bound of $O (lo g n)$ .

math.CO2026

Coloring graphs with no long induced path

Sang-il Oum

Let $P_{t}$ denote the induced path on $t$ vertices. Let $ω (G)$ denote the maximum number of vertices in a clique of a graph $G$ . Gyárfás (1987) proved that every $P_{t}$ -free graph $G…

cs.DM2026

Multiway $f$ -Cut is fixed-parameter tractable

Tony Huynh, Eun Jung Kim, Sang-il Oum +2

A connectivity function on a finite set $E$ is a function $f : 2^{E} \to Z$ that is submodular and symmetric, with $f (\emptyset) = 0$ . Given a connectivity function $f$ via…

math.CO2026

The Excluded Vertex-Minors and Pivot-Minors for Rank-Width at Most Two

Sang-il Oum

We determine both the excluded vertex-minors and the excluded pivot-minors for the class of graphs of rank-width at most two. Up to local equivalence and graph isomorphism, there a…

math.CO2026

A proof of the cycle double cover conjecture by OpenAI: An exposition

Sang-il Oum

The cycle double cover conjecture states that every bridgeless graph has a list of cycles such that every edge is in exactly two of them. In July 2026, OpenAI announced a proof. Th…

cs.LO2026

Formalizing Flag Algebras in Lean

Gyeongwon Jeong, Seonghun Park, Jihoon Hyun +2

Razborov's flag algebra method is one of the most successful tools for proving asymptotic density inequalities in extremal graph theory. It reduces an inequality about all large gr…

math.CO2026

On the chromatic number of the union of comparability graphs

Wouter Cames van Batenburg, Maria Chudnovsky, Linda Cook +3

Resolving in a strong sense a problem of Gyárfás on the union of two perfect graphs, we prove that for every pair of positive integers $d$ and $k$ , there is a graph $G$ with clique…

math.CO2026

Ramsey-type $χ$ -bounds for $χ$ -bounded graph classes

Tung Nguyen, Sang-il Oum

We prove that for every path $P$ , the class of graphs with no induced $P$ and no induced four-cycle $C_{4}$ is linearly $χ$ -bounded. More generally, we ask for which pairs ${T, H}$ …

cs.DS2026

Branch-width of represented matroids in matrix multiplication time

Mujin Choi, Tuukka Korhonen, Sang-il Oum

For an $n$ -element matroid $M$ given by an $n \times n$ matrix representation over a finite field $F$ and an integer $k$ , we present an algorithm with running time $O_{k,\m…

math.CO2026

Polynomial-size encoding of all cuts of small value in integer-valued symmetric submodular functions

Sang-il Oum, Marek Sokołowski

We study connectivity functions, that is, integer-valued symmetric submodular functions on a finite ground set attaining $0$ on the empty set. For a connectivity function $f$ on an…

cs.DS2026

Branch-width of connectivity functions is fixed-parameter tractable

Tuukka Korhonen, Sang-il Oum

A connectivity function on a finite set $V$ is a symmetric submodular function $f : 2^{V} \to Z$ with $f (\emptyset) = 0$ . We prove that finding a branch-decomposition of…

math.CO2025

Blind cop-width and balanced minors of graphs

Hector Buffière, Rutger Campbell, Kevin Hendrey +1

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 loc…

math.CO2025

Unavoidable pivot-minors in graphs of large rank-depth

Jungho Ahn, Kevin Hendrey, O-joung Kwon +1

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-d…

math.CO2025

The Erdős-Pósa property for circle graphs as vertex-minors

Rutger Campbell, J. Pascal Gollin, Meike Hatzel +4

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…

math.CO2024

Colouring t-perfect graphs

Maria Chudnovsky, Linda Cook, James Davies +2

Perfect graphs can be described as the graphs whose stable set polytopes are defined by their non-negativity and clique inequalities (including edge inequalities). In 1975, Chvátal…

math.CO2024

Sharing tea on a graph

J. Pascal Gollin, Kevin Hendrey, Hao Huang +6

Motivated by the analysis of consensus formation in the Deffuant model for social interaction, we consider the following procedure on a graph $G$ . Initially, there is one unit of t…

math.CO2024

Linear bounds on treewidth in terms of excluded planar minors

J. Pascal Gollin, Kevin Hendrey, Sang-il Oum +1

One of the fundamental results in graph minor theory is that for every planar graph $H$ , there is a minimum integer $f (H)$ such that graphs with no minor isomorphic to $H$ have tre…

math.CO2023

Computing pivot-minors

Konrad K. Dabrowski, François Dross, Jisu Jeong +4

A graph $G$ contains a graph $H$ as a pivot-minor if $H$ can be obtained from $G$ by applying a sequence of vertex deletions and edge pivots. Pivot-minors play an important role in…

math.CO2023★ 3 cited

Reuniting $χ$ -boundedness with polynomial $χ$ -boundedness

Maria Chudnovsky, Linda Cook, James Davies +1

A class $F$ of graphs is $χ$ -bounded if there is a function $f$ such that $χ (H) \leq f (ω (H))$ for all induced subgraphs $H$ of a graph in $F$ . If $f$ can be chose…

math.CO2023

Clustered Colouring of Odd- $H$ -Minor-Free Graphs

Robert Hickingbotham, Dong Yeap Kang, Sang-il Oum +2

The clustered chromatic number of a graph class $G$ is the minimum integer $c$ such that every graph $G \in G$ has a $c$ -colouring where each monochromatic compon…

math.CO2023

Note on Hamiltonicity of basis graphs of even delta-matroids

Donggyu Kim, Sang-il Oum

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 $e$ and $f$ sharing a com…

cs.DS2023

Space-Efficient Parameterized Algorithms on Graphs of Low Shrubdepth

Benjamin Bergougnoux, Vera Chekan, Robert Ganian +5

Dynamic programming on various graph decompositions is one of the most fundamental techniques used in parameterized complexity. Unfortunately, even if we consider concepts as simpl…

math.CO2023★ 4 cited

Twin-width of subdivisions of multigraphs

Jungho Ahn, Debsoumya Chakraborti, Kevin Hendrey +1

For each $d \leq 3$ , we construct a finite set $F_{d}$ of multigraphs such that for each graph $H$ of girth at least $5$ obtained from a multigraph $G$ by subdividing each edge at leas…

Every tournament of dichromatic number 10k2 has a vertex whose out-neighborhood has dichromatic number more than k

A double-logarithmic upper bound on the chromatic number of the associahedron

Coloring graphs with no long induced path

Multiway f-Cut is fixed-parameter tractable

The Excluded Vertex-Minors and Pivot-Minors for Rank-Width at Most Two

A proof of the cycle double cover conjecture by OpenAI: An exposition

Formalizing Flag Algebras in Lean

On the chromatic number of the union of comparability graphs

Ramsey-type χ-bounds for χ-bounded graph classes

Branch-width of represented matroids in matrix multiplication time

Polynomial-size encoding of all cuts of small value in integer-valued symmetric submodular functions

Branch-width of connectivity functions is fixed-parameter tractable

Blind cop-width and balanced minors of graphs

Unavoidable pivot-minors in graphs of large rank-depth

The Erdős-Pósa property for circle graphs as vertex-minors

Colouring t-perfect graphs

Sharing tea on a graph

Linear bounds on treewidth in terms of excluded planar minors

Computing pivot-minors

Reuniting χ-boundedness with polynomial χ-boundedness

Clustered Colouring of Odd-H-Minor-Free Graphs

Note on Hamiltonicity of basis graphs of even delta-matroids

Space-Efficient Parameterized Algorithms on Graphs of Low Shrubdepth

Twin-width of subdivisions of multigraphs

Every tournament of dichromatic number $10 k^{2}$ has a vertex whose out-neighborhood has dichromatic number more than $k$

Multiway $f$ -Cut is fixed-parameter tractable

Ramsey-type $χ$ -bounds for $χ$ -bounded graph classes

Reuniting $χ$ -boundedness with polynomial $χ$ -boundedness

Clustered Colouring of Odd- $H$ -Minor-Free Graphs