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