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

Linsong Wei, Yuqi Xu, Yunxia Zhang, Weihua Yang

Published 2023-10-17Version 1

Among graphs with 13 edges, there are exactly three internally 4-connected graphs which are $Oct^{+}$, cube+e and $ K_{3,3} +v$. A complete characterization of all 4-connected graphs with no $Oct^{+}$-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.