On the fine structure of graphs avoiding certain complete bipartite minors

Abstract

Avoiding complete bipartite graphs as minors, and in particular $K_{2,t}$ as a minor, has been used to give sufficient conditions for Hamiltonicity. For this reason and others, the classes of $K_{2,t}$-minor-free graphs are of interest. Ding gave a rough description of the $K_{2,t}$-minor-free graphs that gives necessary conditions for a graph to be $K_{2,t}$-minor-free. We refine this description and characterize the $K_{2,t}$-minor-free graphs in the 3- and 4-connected cases, giving necessary and sufficient conditions. We also give a program for characterizing the 3-connected $K_{2,5}$-minor-free graphs. As part of this program, we prove a result on fan expansions that is of independent interest.