From the 1 of 17 linked papers with an AI index.
17 papers
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…
Formalizing Flag Algebras in Lean
Gyeongwon Jeong, Seonghun Park, Jihoon Hyun +2
Razborov's flag algebra method is a powerful tool for proving asymptotic inequalities in extremal graph theory, often reducing the task to finding a finite certificate by semidefin…
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…
Branch-width of represented matroids in matrix multiplication time
Mujin Choi, Tuukka Korhonen, Sang-il Oum
The paper presents an algorithm that computes a branch-decomposition of a matroid given by a matrix representation in time essentially O(n^ω), improving on previous cubic-time meth…
On the chromatic number of the union of comparability graphs
Maria Chudnovsky, Wouter Cames van Batenburg, 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 cliq…