Rooted $C_5$-Minors

Abstract

Let $G$ be a graph and $x_1,x_2,\dots ,x_k$ be distinct vertices of $G$. We say $(G,x_1{x}_2\dots x_k)$ has a $C_k$-minor or $G$ has a $C_k$-minor rooted at $x_1{x}_2\dots x_k$, if there exist pairwise disjoint sets $X_1,X_2,\dots ,X_k\subseteq V(G)$, such that for all $i\in [k]$, $G[X_i]$ is connected, $x_i\in X_i$, and $G$ has an edge between $X_i$ and $X_{i+1}$, where $X_{k+1}=X_k$. When $k=3$ it is easy to determine when $(G,x_1{x}_2{x}_3)$ contains a $C_3$-minor. For $k=4$, Robertson, Seymour and Thomas gave a characterization of $(G,x_1{x}_2{x}_3{x}_4)$ with no $C_4$-minor, which, in particular, implies that such $G$ has connectivity at most 5. In this paper, we apply a method of Thomas and Wollan to prove a result, which implies that if $G$ is $10$-connected then, for all distinct vertices $x_1,x_2,x_3,x_4,x_5$ of $G$, $(G,x_1{x}_2{x}_3{x}_4{x}_5)$ has a $C_5$-minor.

14 pages