47 citations · 678 across the 85 of their papers we have counts for
72 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…
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…
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 …
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…
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…
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 , every graph of sufficiently large rank-d…
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 with at least one edge and for any positive integer , there exists an integer so that every graph either has a vertex-minor…
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…
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 . Initially, there is one unit of t…
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 , there is a minimum integer such that graphs with no minor isomorphic to have tre…
Computing pivot-minors
Konrad K. Dabrowski, François Dross, Jisu Jeong +4
A graph contains a graph as a pivot-minor if can be obtained from by applying a sequence of vertex deletions and edge pivots. Pivot-minors play an important role in…
Reuniting -boundedness with polynomial -boundedness
Maria Chudnovsky, Linda Cook, James Davies +1
A class of graphs is -bounded if there is a function such that for all induced subgraphs of a graph in . If can be chose…
Clustered Colouring of Odd--Minor-Free Graphs
Robert Hickingbotham, Dong Yeap Kang, Sang-il Oum +2
The clustered chromatic number of a graph class is the minimum integer such that every graph has a -colouring where each monochromatic compon…
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 and sharing a com…
Twin-width of subdivisions of multigraphs
Jungho Ahn, Debsoumya Chakraborti, Kevin Hendrey +1
For each , we construct a finite set of multigraphs such that for each graph of girth at least obtained from a multigraph by subdividing each edge at leas…
Twin-width of random graphs
Jungho Ahn, Debsoumya Chakraborti, Kevin Hendrey +2
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 su…
A unified Erdős-Pósa theorem for cycles in graphs labelled by multiple abelian groups
J. Pascal Gollin, Kevin Hendrey, O-joung Kwon +2
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…
Independent domination of graphs with bounded maximum degree
Eun-Kyung Cho, Jinha Kim, Minki Kim +1
An independent dominating set of a graph, also known as a maximal independent set, is a set of pairwise non-adjacent vertices such that every vertex not in is adjacent to s…
Prime vertex-minors of a prime graph
Donggyu Kim, Sang-il Oum
A graph is prime if it does not admit a partition of its vertex set such that and the rank of the submatrix of its adjacency matrix is…
A chain theorem for sequentially -rank-connected graphs with respect to vertex-minors
Duksang Lee, Sang-il Oum
Tutte (1961) proved the chain theorem for simple -connected graphs with respect to minors, which states that every simple -connected graph has a simple -connected mino…