Rank connectivity and pivot-minors of graphs
In: European J. Combin., 108:103634, February 2023; (2020)
Online
report
Zugriff:
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$, $\lvert X\rvert$ or $\lvert V(G)-X\rvert $ 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 $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.
Comment: 23 pages, 1 figure. Accepted to the European Journal of Combinatorics
Titel: |
Rank connectivity and pivot-minors of graphs
|
---|---|
Autor/in / Beteiligte Person: | Oum, Sang-il |
Link: | |
Quelle: | European J. Combin., 108:103634, February 2023; (2020) |
Veröffentlichung: | 2020 |
Medientyp: | report |
DOI: | 10.1016/j.ejc.2022.103634 |
Schlagwort: |
|
Sonstiges: |
|