A characterization of 4-connected graphs with no $K_{3,3}+v$-minor

Abstract

Among graphs with 13 edges, there are exactly three internally 4-connected graphs which are $Oc{t}^{+}$, cube+e and $K_{3,3}+v$. A complete characterization of all 4-connected graphs with no $Oc{t}^{+}$-minor is given in [John Maharry, An excluded minor theorem for the octahedron plus an edge, Journal of Graph Theory 57(2) (2008) 124-130]. Let $K_{3,3}+v$ denote the graph obtained by adding a new vertex $v$ to $K_{3,3}$ and joining $v$ to the four vertices of a 4-cycle. In this paper, we determine all 4-connected graphs that do not contain $K_{3,3}+v$ as a minor.

25