Rank connectivity and pivot-minors of graphs

Abstract

© 2022 Elsevier LtdThe cut-rank of a set X in a graph G is the rank of the X×(V(G)−X) submatrix of the adjacency matrix over the binary field. A split is a partition of the vertex set into two sets (X,Y) such that the cut-rank of X is less than 2 and both X and Y have at least two vertices. A graph is prime (with respect to the split decomposition) if it is connected and has no splits. A graph G is k+ℓ-rank-connected if for every set X of vertices with the cut-rank less than k, |X| or |V(G)−X| is less than k+ℓ. We prove that every prime 3+2-rank-connected graph G with at least 10 vertices has a prime 3+3-rank-connected pivot-minor H such that |V(H)|=|V(G)|−1. As a corollary, we show that every excluded pivot-minor for the class of graphs of rank-width at most k has at most (3.5⋅6k−1)/5 vertices for k≥2. We also show that the excluded pivot-minors for the class of graphs of rank-width at most 2 have at most 16 vertices.