IBS Discrete Mathematics Group 기초과학연구원 이산수학그룹

Calum Buchanan, *Alexander Clifton*, Eric Culver, Péter Frankl, Jiaxi Nie, Kenta Ozeki, Puck Rombach, and Mei Yin,
On odd covers of cliques and disjoint unions, J. Graph Theory, accepted, 2026.

On odd covers of cliques and disjoint unions Babai and Frankl posed the ``odd cover problem" of finding the minimum cardinality of a collection of complete bipartite graphs such that every edge of the complete graph of order $n$ is covered an odd number of times. In a previous paper with O'Neill, some of the authors proved that this value is a...

Stefan Weltge gave a talk on the minimum number of inequalities whose integer solutions are standard unit vectors at the Discrete Math Seminar

On June 19, 2026, Stefan Weltge from the Technical University of Munich gave a talk at the Discrete Math Seminar on the minimum number of inequalities whose integer solutions are precisely standard unit vectors. The title of his talk was "The relaxation complexity of the standard simplex is logarithmic". https://www.youtube.com/watch?v=PBRsNr64aPA

https://dimag.ibs.re.kr/2026/relaxation-complexity/

Stefan Weltge gave a talk on the minimum number of inequalities whose integer solutions are standard unit vectors at the Discrete Math Seminar - Discrete Mathematics Group On June 19, 2026, Stefan Weltge from the Technical University of Munich gave a talk at the Discrete Math Seminar on the minimum number of inequalities whose integer solutions are … Continue reading "Stefan Weltge gave a talk on the minimum number of inequalities whose integer solutions are standar...

Jakob Greilhuber and *Roohani Sharma*,
A dividing line for structural kernelization of component order connectivity via distance to bounded pathwidth,
In the Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science (MFCS2026, August 24-28, 2026, Paris, France), accepted, 2026

A Dividing Line for Structural Kernelization of Component Order Connectivity via Distance to Bounded Pathwidth In this work we study a classic generalization of the Vertex Cover (VC) problem, called the Component Order Connectivity (COC) problem. In COC, given an undirected graph $G$, integers $d \geq 1$ and $k$, the goal is to determine if there is a set of at most $k$ vertices whose deletion results in a g...

Kenny Bešter Štorgel, *Mujin Choi*, Hidde Koerts, and Ðorđe Vasić,
Tree-independence number of $K_{1,d}$-free graph classes, 2026.

Tree-independence number of $K_{1,d}$-free graph classes In this paper, we investigate the tree-independence number of graph classes that do not contain $K_{1,d}$ as an induced subgraph. Dallard et al. conjectured that for any positive integer $d$ and any planar graph $H$, the class of all $K_{1,d}$-free graphs without $H$ as an induced minor has bounded....

Harry Richman gave a talk on an algorithm to compute tropical Weierstrass weights at the Discrete Math Seminar

On June 16, 2026, Harry Richman gave a talk on an algorithm to compute tropical Weierstrass weights at the Discrete Math Seminar. The title of his talk was "Distinguishing graphs with tropical Weierstrass weights".

Harry Richman gave a talk on an algorithm to compute tropical Weierstrass weights at the Discrete Math Seminar - Discrete Mathematics Group On June 16, 2026, Harry Richman gave a talk on an algorithm to compute tropical Weierstrass weights at the Discrete Math Seminar. The title of his talk was “Distinguishing graphs … Continue reading "Harry Richman gave a talk on an algorithm to compute tropical Weierstrass weights at the Discrete...

*J. Pascal Gollin*, *Kevin Hendrey*, Hao Huang, *Tony Huynh*, Bojan Mohar, *Sang-il Oum*, Ningyuan Yang, Wei-Hsuan Yu, and Xuding Zhu,
Sharing tea on a graph,
Comb. Theory, accepted, 2026.

Sharing tea on a graph 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 tea at a fixed vertex $r \in V(G)$, and all other vertices have no tea. At any time in the procedure, we can choose a con...

J. Pascal Gollin gave a talk on the existence of a balanced separator dominated by small number of vertices in a graph excluding a wheel as an induced minor at the Discrete Math Seminar

On June 9, 2026, J. Pascal Gollin from University of Primorska gave a talk at the Discrete Math Seminar on the existence of a balanced separator dominated by small number of vertices in a graph excluding a wheel as an induced minor. The title of his talk was "Dominated balanced separators in wheel-induced-minor-free graphs".

J. Pascal Gollin gave a talk on the existence of a balanced separator dominated by small number of vertices in a graph excluding a wheel as an induced minor at the Discrete Math Seminar - Discrete Mathematics Group On June 9, 2026, J. Pascal Gollin from University of Primorska gave a talk at the Discrete Math Seminar on the existence of a balanced separator dominated by small number … Continue reading "J. Pascal Gollin gave a talk on the existence of a balanced separator dominated by small number of vertices...

Maria Chudnovsky, Linda Cook, James Davies, *Seokbeom Kim*, and *Sang-il Oum*,
On the chromatic number of the union of comparability graphs, 2026.

On the chromatic number of the union of comparability graphs Resolving in a strong sense an old problem of Gyárfás from the 1980s 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 number $k$ and chromatic number $k^d$ that is the union of $d$ comparability graphs.

Matthew Baker, Changxin Ding, and *Donggyu Kim*,
The Jacobian of a regular orthogonal matroid and torsor structures on spanning quasi-trees of ribbon graphs,
Adv. Math., accepted, 2026.

The Jacobian of a regular orthogonal matroid and torsor structures on spanning quasi-trees of ribbon graphs Previous work of Chan--Church--Grochow and Baker--Wang shows that the set of spanning trees in a plane graph $G$ is naturally a torsor for the Jacobian group of $G$. Informally, this means that the set of spanning trees of $G$ naturally forms a group, except that there is no distinguished identity e...

Maria Chudnovsky gave a talk on bounding treewidth of n-vertex graphs excluding fixed induced minors as a function of n at the Discrete Math Seminar

On June 2, 2026, Maria Chudnovsky from Princeton University gave a talk on bounding treewidth of n-vertex graphs excluding fixed induced minors as a function of n at the Discrete Math Seminar. The title of her talk was "Induced minors and treewidth".

Maria Chudnovsky gave a talk on bounding treewidth of n-vertex graphs excluding fixed induced minors as a function of n at the Discrete Math Seminar - Discrete Mathematics Group On June 2, 2026, Maria Chudnovsky from Princeton University gave a talk on bounding treewidth of n-vertex graphs excluding fixed induced minors as a function of n at the Discrete … Continue reading "Maria Chudnovsky gave a talk on bounding treewidth of n-vertex graphs excluding fixed induced minor...