The cut-rank of a set $X$ in a graph $G$ is the rank of the $Xtimes (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$, $lvert Xrvert$ or $lvert V(G)-Xrvert $ 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 $lvert V(H)rvert =lvert V(G)rvert -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 $kge 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.
تحميل البحث