The Excluded Vertex-Minors and Pivot-Minors for Rank-Width at Most Two

Abstract

We determine both the excluded vertex-minors and the excluded pivot-minors for the class of graphs of rank-width at most two. Up to local equivalence and graph isomorphism, there are exactly 25 excluded vertex-minors: 1 graph on 8 vertices, 18 on 9 vertices, and 6 on 10 vertices. Up to pivot equivalence and graph isomorphism, there are exactly 609 excluded pivot-minors: 2 on 8 vertices, 447 on 9 vertices, 146 on 10 vertices, 10 on 11 vertices, and 4 on 12 vertices. No excluded vertex-minor occurs on 11--16 vertices, and no excluded pivot-minor occurs on 13--16 vertices; the author's 16-vertex bound makes both lists complete. The proof is computer-assisted. Instead of enumerating all graphs, we reverse the one-vertex reduction theorem for prime graphs. For each $n$, we retain exactly the prime $n$-vertex graphs of rank-width at most two, modulo local equivalence and isomorphism, and extend those graphs by one vertex. Local-equivalence classes are identified by an exact canonical key obtained from the associated isotropic system, the binary row space of $[I\mid A(G)]$. A restricted version of the same key classifies pivot equivalence exactly. The vertex-minor and pivot-minor computations examine, respectively, more than $9.0\times 10^{10}$ and $4.9\times 10^{11}$ prime extensions in their 16-vertex final layers.

Disclosure

“minors. The resulting frontier may still grow rapidly, but the framework separates the mathematical completeness argument from parallelization and other search-specific optimizations. Statement of AI use. The author used OpenAI’s GPT-5.6 Sol and Anthropic’s Claude Fable 5 for programming assistance, monitoring computations, drafting, and editorial suggestions. The author independently verified the mathematical arguments, source code, computations, and final text and takes”

PDF page 24

Classification

Proof ideas or individual proof-step assistance

Multiplier

8

Verified

2026-08-23T19:06:34.816867Z

Structural counts