Moderately beyond clique-width: reduced component max-leaf and related parameters Reduced parameters [BKW, JCTB '26; BKRT, SODA '22] are defined via contraction sequences. Based on this framework, we introduce the reduced component max-leaf, denoted by $\operatorname{cml}^\downarro...

#New_arXiv_paper
Édouard Bonnet, Yeonsu Chang, Julien Duron, *Colin Geniet*, and *O-joung Kwon*,
Moderately beyond clique-width: reduced component max-leaf and related parameters, 2026.
arxiv.org/abs/2604.19138

Quickly excluding an annotated planar graph We provide proofs certifying that the structure theorem for vertex sets of bounded bidimensionality holds with polynomial bounds. The bidimensionality of vertex sets is a common generalisation of both...

#New_accepted_conference_paper
Édouard Bonnet, *Colin Geniet*, *Eun Jung Kim*, and Sungmin Moon,
Fast shortest path in graphs with sparse signed tree models and applications,
ICALP 2026 (Royal Holloway, University of London. London, UK, July 7-10), accepted, 2026.
arxiv.org/abs/2602.06516

#New_accepted_conference_paper
*Maximilian Gorsky*, Evangelos Protopapas and Sebastian Wiederrecht,
Quickly excluding an annotated planar graph,
In the Proceedings of ICALP 2026 (Royal Holloway, University of London. London, UK, July 7-10), accepted, 2026.

#New_accepted_conference_paper
*Maximilian Gorsky*, Michał Seweryn, and Sebastian Wiederrecht,
The price of homogeneity is polynomial,
In the Proceedings of ICALP 2026 (Royal Holloway, University of London. London, UK, July 7-10), accepted, 2026.

#New_accepted_conference_paper
*Mujin Choi*, *Maximilian Gorsky*, *Gunwoo Kim*, Caleb McFarland, and Sebastian Wiederrecht,
Odd-Cycle-Packing-treewidth: On the Maximum Independent Set problem in odd-minor-free graph classes,
In the Proceedings of ICALP 2026, London, UK, July 7-10), accepted, 2026.

Mamadou Moustapha Kanté gave a talk on characterizing strongly flip-flat graph classes without a large complete bipartite subgraph at the Discrete Math Seminar On April 7, 2026, Mamadou Moustapha Kanté from Université Clermont Auvergne gave a talk at the Discrete Math Seminar on characterizing strongly flip-flat graph classes without a large biclique. The title of his talk was "Strongly flip-flat classes of graphs".

Mamadou Moustapha Kanté gave a talk on characterizing strongly flip-flat graph classes without a large complete bipartite subgraph at the Discrete Math Seminar

On April 7, 2026, Mamadou Moustapha Kanté from Université Clermont Auvergne gave a talk at the Discrete Math Seminar on characterizing…

Welcome Marguerite Bin, a new graduate student of the IBS Discrete Mathematics Group The IBS Discrete Mathematics Group welcomes Marguerite Bin, a new graduate student of the Discrete Mathematics Group from April 2, 2026 to May 26, 2026. She is a Ph.D. student at Université de Lorraine. Her advisor is Xavier Goaoc.

Welcome Marguerite Bin, a new graduate student of the IBS Discrete Mathematics Group

The IBS Discrete Mathematics Group welcomes Marguerite Bin, a new graduate student of the Discrete Mathematics Group from April 2, 2026 to May 26, 2026. She is a Ph.D. student at Université de Lorraine. Her…

Tung Nguyen gave a talk on polynomial 𝛘-boundedness of P_5-free graphs at the Discrete Math Seminar On March 31, 2026, Tung Nguyen from the University of Oxford gave a talk at the Discrete Math Seminar on polynomial 𝛘-boundedness of graphs with no induced path on 5 vertices. The title of his talk was "Polynomial χ-boundedness for excluding the five-vertex path".

Tung Nguyen gave a talk on polynomial 𝛘-boundedness of P_5-free graphs at the Discrete Math Seminar

On March 31, 2026, Tung Nguyen from the University of Oxford gave a talk at the Discrete Math Seminar on polynomial 𝛘-boundedness of graphs with no induced path on 5 vertices. The title of his talk…

Colorful fractional Helly theorem via weak saturation Two celebrated extensions of the classical Helly's theorem are the fractional Helly theorem and the colorful Helly theorem. Bulavka, Goodarzi, and Tancer recently established the optimal bound for the...

#New_accepted_paper
Debsoumya Chakraborti, Minho Cho, *Jinha Kim*, and Minki Kim,
Colorful fractional Helly theorem via weak saturation,
Electron. J. Combin., accepted, 2026.
arxiv.org/abs/2408.15093

The Four Color Theorem with Linearly Many Reducible Configurations and Near-Linear Time Coloring We give a near-linear time 4-coloring algorithm for planar graphs, improving on the previous quadratic time algorithm by Robertson et al. from 1996. Such an algorithm cannot be achieved by the known p...

4색 정리 새로운 증명이 arXiv에 올라왔습니다.
New proof of the four color theorem
by
Yuta Inoue, Ken-ichi Kawarabayashi, Atsuyuki Miyashita, Bojan Mohar, Carsten Thomassen, Mikkel Thorup
arxiv.org/abs/2603.24880

Hidde Koerts gave a talk on characterizing tournaments with no backedge graph of small clique number at the Discrete Math Seminar On March 24, 2026, Hidde Koerts from the University of Waterloo gave a talk at the Discrete Math Seminar on characterizing tournaments with no backedge graph of small clique number. The title of his talk was "Characterizing large clique number in tournament".

Hidde Koerts gave a talk on characterizing tournaments with no backedge graph of small clique number at the Discrete Math Seminar

On March 24, 2026, Hidde Koerts from the University of Waterloo gave a talk at the Discrete Math Seminar on characterizing tournaments with no backedge graph of small…

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 $...

#New_arXiv_paper
Jakob Greilhuber and *Roohani Sharma*,
A dividing line for structural kernelization of component order connectivity via distance to bounded pathwidth, 2026.
arxiv.org/abs/2603.22240

$f$-Diophantine sets over finite fields via quasi-random hypergraphs from multivariate polynomials We investigate $f$-Diophantine sets over finite fields via new explicit constructions of families of quasi-random hypergraphs from multivariate polynomials. In particular, our construction not only of...

#New_accepted_paper
Seoyoung Kim, Chi Hoi Yip, and *Semin Yoo*,
f-Diophantine sets over finite fields via quasi-random hypergraphs from multivariate polynomials,
Mathematika, accepted, 2026.
arxiv.org/abs/2503.19603

A lower bound on the number of edges in DP-critical graphs A graph $G$ is $k$-critical (list $k$-critical, DP $k$-critical) if $χ(G)= k$ ($χ_\ell(G)= k$, $χ_\mathrm{DP}(G)= k$) and for every proper subgraph $G'$ of $G$, $χ(G')<k$ ($χ_\ell(G')< k$, $χ_\mathrm{...

#New_accepted_paper
Peter Bradshaw, *Ilkyoo Choi*, Alexandr Kostochka, and Jingwei Xu,
A lower bound on the number of edges in DP-critical graphs,
J. Combin. Theory Ser. B, accepted, 2026.
arxiv.org/abs/2409.00937

József Balogh gave a talk on decomposing (or covering) the edge set of a graph into (or by) cliques at the Discrete Math Seminar On March 12, 2026, József Balogh from the University of Illinois at Urbana-Champaign gave a talk on decomposing the edge set of a graph into edge sets of clliques or covering by edge sets of cliques at the Discrete Math Seminar. The title of his talk was "Clique covers and decompositions of cliques of graphs".

József Balogh gave a talk on decomposing (or covering) the edge set of a graph into (or by) cliques at the Discrete Math Seminar

On March 12, 2026, József Balogh from the University of Illinois at Urbana-Champaign gave a talk on decomposing the edge set of a graph into edge sets of clliques or…

Polynomial-size encoding of all cuts of small value in integer-valued symmetric submodular functions 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 $n$-element set $V$...

#New_arXiv_paper
*Sang-il Oum* and Marek Sokołowski,
Polynomial-size encoding of all cuts of small value in integer-valued symmetric submodular functions, 2026.
arxiv.org/abs/2603.10710

Dario Cavallaro gave a talk on well-quasi-ordering of Eulerian digraphs under (strong) immersion at the Discrete Math Seminar On March 10, 2026, Dario Cavallaro from the TU Berlin gave a talk at the Discrete Math Seminar on well-quasi-ordering of Eulerian digraphs under (strong) immersion. The title of his talk was "Well-quasi-ordering Eulerian directed graphs by (strong) immersion".

Dario Cavallaro gave a talk on well-quasi-ordering of Eulerian digraphs under (strong) immersion at the Discrete Math Seminar

On March 10, 2026, Dario Cavallaro from the TU Berlin gave a talk at the Discrete Math Seminar on well-quasi-ordering of Eulerian digraphs under (strong) immersion. The…

New Strides Made on Deceptively Simple ‘Lonely Runner’ Problem | Quanta Magazine A straightforward conjecture about runners moving around a track turns out to be equivalent to many complex mathematical questions. Three new proofs mark the first significant progress on the problem ...

As runners move around a track, are they bound to end up “lonely”? Three new proofs suggest the answer is yes — the first significant progress on the problem in decades.
www.quantamagazine.org/new-strides-...

Post Image

Chính T. Hoàng gave a survey talk on graph coloring and forbidden induced subgraphs at the Discrete Math Seminar

On March 3, 2026, Chính T. Hoàng from the Wilfrid Laurier University, Waterloo, Canada gave a survey talk on graph coloring and…

https://dimag.ibs.re.kr/2026/chinh-t-hoang-seminar/

Variants of Merge-Width and Applications Merge-width is a recently introduced family of graph parameters that unifies treewidth, clique-width, twin-width, and generalised colouring numbers. We prove the equivalence of several alternative def...

#New_arXiv_paper
Karolina Drabik, Maël Dumas, *Colin Geniet*, Jakub Nowakowski, Michał Pilipczuk, and Szymon Toruńczyk,
Variants of Merge-Width and Applications, 2026.
arxiv.org/abs/2602.23867

Triangulated spheres with holes in triangulated surfaces Let $\mathbb{S}_h$ denote a sphere with $h$ holes. Given a triangulation $G$ of a surface $\mathbb{M}$, we consider the question of when $G$ contains a spanning subgraph $H$ such that $H$ is a triangu...

#New_accepted_paper
Katie Clinch, Sean Dewar, Niloufar Fuladi, *Maximilian Gorsky*, *Tony Huynh*, Eleftherios Kastis, Atsuhiro Nakamoto, Anthony Nixon, and Brigitte Servatius,
Triangulated spheres with holes in triangulated surfaces,
Discrete Comput. Geom., accepted, 2026.
arxiv.org/abs/2410.04450

Towers and Bratteli-Vershik systems in Fibonacci-like unimodal maps For a class of Fibonacci-like unimodal maps, the restriction to the $ω$-limit set of the unique turning point defines a minimal Cantor system. We construct these Cantor sets geometrically using a nest...

#New_arXiv_paper
Jorge Olivares-Vinales and *Semin Yoo*,
Towers and Bratteli-Vershik systems in Fibonacci-like unimodal maps, 2026.
arxiv.org/abs/2602.21623

Shifted multiplicative subgroups are not ratio sets In a recent breakthrough, Kalmynin proved a conjecture of Lev--Sonn and a conjecture of Sárközy on additive decompositions of multiplicative subgroups of a prime field. In this paper, we prove a multi...

#New_arXiv_paper
Seoyoung Kim, Chi Hoi Yip, and *Semin Yoo*,
Shifted multiplicative subgroups are not ratio sets, 2026.
arxiv.org/abs/2602.20919

Post Image

Marek Sokołowski gave a talk on a new parallel algorithm computing single-source shortest paths in directed graphs at the Discrete Math Seminar

On February 24, 2026, Marek Sokołowski from the Max Planck Institute of Informatics gave a talk at…

https://dimag.ibs.re.kr/2026/marek-sokolowski-seminar/

Complexity lower bounds for succinct binary structures of bounded clique-width with restrictions We present a Rice-like complexity lower bound for any MSO-definable problem on binary structures succinctly encoded by circuits. This work extends the framework recently developed as a counterpoint to...

#New_arXiv_paper
*Colin Geniet*, Aliénor Goubault-Larrecq, and Kévin Perrot,
Complexity lower bounds for succinct binary structures of bounded clique-width with restrictions, 2026.
arxiv.org/abs/2602.18240

Fast Shortest Path in Graphs With Sparse Signed Tree Models and Applications A signed tree model of a graph $G$ is a compact binary structure consisting of a rooted binary tree whose leaves are bijectively mapped to the vertices of $G$, together with 2-colored edges $xy$, call...

#New_arXiv_paper
Édouard Bonnet, *Colin Geniet*, *Eun Jung Kim*, and Sungmin Moon,
Fast shortest path in graphs with sparse signed tree models and applications, 2026.
arxiv.org/abs/2602.16605

On a variant of dichromatic number for digraphs with prescribed sets of arcs In this paper, we consider a variant of dichromatic number on digraphs with prescribed sets of arcs. Let $D$ be a digraph and let $Z_1, Z_2$ be two sets of arcs in $D$. For a subdigraph $H$ of $D$, le...

#New_accepted_paper
*O-joung Kwon* and Xiaopan Lian,
On a variant of dichromatic number for digraphs with prescribed sets of arcs,
Graphs and Combinatorics, accepted, 2026.
arxiv.org/abs/2307.05897

Post Image

Seonghun Park (박성훈) gave a talk on formalizing the flag algebra in the lean theorem prover

On February 10, 2026, Seonghun Park (박성훈) from KAIST gave a talk on formalizing the flag algebra introduced by Alexander Razborov in the lean theorem…

dimag.ibs.re.kr/2026/seonghun-park-flag-...

First-Order Logic and Twin-Width for Some Geometric Graphs For some geometric graph classes, tractability of testing first-order formulas is precisely characterised by the graph parameter twin-width. This was first proved for interval graphs among others in [...

#New_accepted_conference_paper
*Colin Geniet*, *Gunwoo Kim*, and Lucas Meijer,
First-Order Logic and Twin-Width for Some Geometric Graphs,
In the Proceedings of the 42nd International Symposium on Computational Geometry (SoCG 2026), accepted, 2026.
arxiv.org/abs/2512.21896

On non-planar, cycle-conformal graphs A graph $G$ is called matching covered if all of its edges are contained in some perfect matching of $G$. Furthermore, a cycle $C \subseteq G$ is called conformal if $G - V(C)$ has a perfect matching ...

#New_arXiv_paper
*Maximilian Gorsky* and Clemens Kuske,
On non-planar, cycle-conformal graphs, 2026.
arxiv.org/abs/2602.07331