Rank connectivity and pivot-minors of graphs

Abstract

The cut-rank of a set $X$ in a graph $G$ is the rank of the $X\times (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^{+\ell }$-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+\ell$. 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\cdot 6^k-1)/5$ vertices for $k\ge 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.

23 pages, 1 figure. Accepted to the European Journal of Combinatorics

Cited by in corpus (2)

• A chain theorem for sequentially $3$-rank-connected graphs with respect to vertex-minors
• Intertwining connectivities for vertex-minors and pivot-minors