BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv6.18.0//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
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: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