Linkages and removable paths avoiding vertices

Abstract

We say that a graph $G$ is $(2,m)$-linked if, for any distinct vertices $a_1,\dots ,a_m,b_1,b_2$ in $G$, there exist vertex disjoint connected subgraphs $A,B$ of $G$ such that $\{a_1,\dots ,a_m\}$ is contained in $A$ and $\{b_1,b_2\}$ is contained in $B$. A fundamental result in structural graph theory is the characterization of $(2,2)$-linked graphs, with different versions obtained independently by Robertson and Chakravarty, Seymour, and Thomassen. It appears to be very difficult to characterize $(2,m)$-linked graphs for $m\ge 3$. In this paper, we provide a partial characterization of $(2,m)$-linked graphs by adding an average degree condition. This implies that $(2m+2)$-connected graphs are $(2,m)$-linked. Moreover, if $G$ is a $(2m+2)$-connected graph and $a_1,\dots ,a_m,b_1,b_2$ are distinct vertices of $G$, then there is a path $P$ in $G$ between $b_1$ and $b_2$ and avoiding $\{a_1,\dots ,a_m\}$ such that $G-P$ is connected, improving a previous connectivity bound of $10m$.

17 pages