BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv6.18.0//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:Discrete Mathematics Group
X-ORIGINAL-URL:https://dimag.ibs.re.kr
X-WR-CALDESC:Events for Discrete Mathematics Group
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:Asia/Seoul
BEGIN:STANDARD
TZOFFSETFROM:+0900
TZOFFSETTO:+0900
TZNAME:KST
DTSTART:20250101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20261013T163000
DTEND;TZID=Asia/Seoul:20261013T173000
DTSTAMP:20260819T090026Z
CREATED:20260811T214705Z
LAST-MODIFIED:20260819T090026Z
UID:13078-1791909000-1791912600@dimag.ibs.re.kr
SUMMARY:Julien Codsi\, Recent progress in the tree-⍺ world
DESCRIPTION:Treewidth is a graph parameter commonly used to quantify how “close” a graph is to a tree. Although it is a cornerstone of structural graph theory and algorithm design\, it is nearly useless for algorithmic purposes in many dense graph classes. In this talk\, we discuss the tree-independence number\, a more versatile graph parameter that replaces the standard width measure with the stability number. We will present recent results aimed at characterizing the graph classes in which this parameter enables sub-exponential time algorithms for problems that are\, in general\, NP-hard.
URL:https://dimag.ibs.re.kr/event/2026-10-13/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20261027T163000
DTEND;TZID=Asia/Seoul:20261027T173000
DTSTAMP:20261001T042132Z
CREATED:20260917T075544Z
LAST-MODIFIED:20261001T042132Z
UID:13361-1793118600-1793122200@dimag.ibs.re.kr
SUMMARY:Xiying Du\, Characterizing (2\,3)-linked graphs
DESCRIPTION:We say a graph $G$ is $(2\,m)$-linked if\, for every choice of $m+2$ distinct vertices $a_1\,\ldots\,a_m\,b_1\,b_2$ in $G$\, there exist two vertex-disjoint connected subgraphs $A$ and $B$ of $G$ such that $\{a_1\,\ldots\,a_m\}\subseteq V(A)$ and $\{b_1\,b_2\}\subseteq V(B)$. A related notion is $k$-linkedness: a graph is $k$-linked if\, for any distinct vertices $s_1\,\ldots\,s_k\,t_1\,\ldots\,t_k$\, it contains $k$ pairwise vertex-disjoint paths joining $s_i$ to $t_i$ for $i=1\,\ldots\,k$. \nA fundamental result in graph theory is the characterization of $2$-linked graphs\, obtained independently by Robertson and Chakravarti\, Seymour\, and Thomassen: $G$ does not contain disjoint paths joining $s_1$ to $t_1$ and $s_2$ to $t_2$ if and only if $G$ admits a certain “essentially planar” structure with $s_1\,s_2\,t_1\,t_2$ appearing on the outer boundary in this cyclic order. For $k$-linkedness and $(2\,m)$-linkedness with $k\,m\geq 3$\, comparable complete structural characterizations seem much more difficult. \nIn this talk\, I will present a full structural characterization of $(2\,3)$-linked graphs. This is joint work with Robin Thomas\, Shijie Xie\, and Xingxing Yu.
URL:https://dimag.ibs.re.kr/event/2026-10-27/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR