Unavoidable minors of graphs of large type (Q1598813): Difference between revisions

The type of a graph \(G\) is a measure of the complexity of the graph. Specifically, the type of \(G\) is the least number \(n\) such that a graph with no edges can be obtained from \(G\) in a sequence of \(n\) steps each of which conists of deleting or contracting a single edge from each block of the current graph. The authors prove that a \(3\)-connected graph has large type if and only if it has a large fan as a minor, where the fan \(F_n\) is obtained from an \(n\)-vertex path by adding a new vertex and joining this vertex to every vertex of the path. In addition, the authors prove that, for all \(n\) exceeding \(3\), there is a number \(N\) such that every graph of type at least \(N\) has a minor isomorphic to \(F_n\) or to \(C_{n,n}\) or its planar dual, where \(C_{n,n}\) is obtained from an \(n\)-cycle by replacing every edge by \(n\) edges in parallel.