On October 27, 2026, Xiying Du (都汐滢) from the IBS Discrete Mathematics Group gave a talk at the Discrete Math Seminar on the characterization of graphs admitting two disjoint connected subgraphs containing X and Y, respectively, for any pair (X,Y) of vertex sets of size 2 and 3. The title of her talk was “Characterizing (2,3)-linked graphs“.
Xiying Du, Characterizing (2,3)-linked graphs
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$.
A 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.
In 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.
Welcome Xiying Du, a new member of the IBS Discrete Mathematics Group
The IBS Discrete Mathematics Group welcomes Dr. Xiying Du (都汐滢), a new research fellow at the IBS Discrete Mathematics Group, starting on September 1, 2026.
She received her Ph.D. from the Georgia Institute of Technology under the supervision of Prof. Rose McCarty and Prof. Xingxing Yu. She is interested in structural graph theory, in particular graph linkages, degree-boundedness, and induced subgraphs.



