A characterization of 4-connected graphs with no K_3,3+v-minor

2023/10/17 by Wei, Linsong, Xu, Yuqi, Yang, Weihua +1
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2310.12283

Abstract

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.

Related

• Graphs without large K_2,n-minors
• On minors of non-hamiltonian graphs
• An excluded minor theorem for the Wagner graph plus an edge
• A characterization of K_2,4-minor-free graphs
• On the number of graphs not containing K_3,3 as a minor