47 citations · 678 across the 85 of their papers we have counts for
12 papers · 1 filter
Every tournament of dichromatic number has a vertex whose out-neighborhood has dichromatic number more than
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…
A double-logarithmic upper bound on the chromatic number of the associahedron
Sang-il Oum, David R. Wood
We show that the associahedron has chromatic number , improving on the previously best known upper bound of .
Coloring graphs with no long induced path
Sang-il Oum
Let denote the induced path on vertices. Let denote the maximum number of vertices in a clique of a graph . Gyárfás (1987) proved that every -free graph $G…
Multiway -Cut is fixed-parameter tractable
Tony Huynh, Eun Jung Kim, Sang-il Oum +2
A connectivity function on a finite set is a function that is submodular and symmetric, with . Given a connectivity function via…
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…
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…
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…
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 and , there is a graph with clique…
Ramsey-type -bounds for -bounded graph classes
Tung Nguyen, Sang-il Oum
We prove that for every path , the class of graphs with no induced and no induced four-cycle is linearly -bounded. More generally, we ask for which pairs …
Branch-width of represented matroids in matrix multiplication time
Mujin Choi, Tuukka Korhonen, Sang-il Oum
For an -element matroid given by an matrix representation over a finite field and an integer , we present an algorithm with running time $O_{k,\m…
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 on the empty set. For a connectivity function on an…
Branch-width of connectivity functions is fixed-parameter tractable
Tuukka Korhonen, Sang-il Oum
A connectivity function on a finite set is a symmetric submodular function with . We prove that finding a branch-decomposition of…