3
Vertex-minors of complete graphs are either complete graphs, star graphs, or edgeless graphs, so this does not hold for $k \ge 2$.
Proof that vertex-minors of complete graphs are complete, star, or edgeless: From a complete graph, vertex deletion gives a complete graph and local complementation gives a star graph. From a star graph, deletion of the central ...
1
Maybe this will give ideas for a faster algorithm:
Theorem 1. There's an $O(n^2 \log n)$-time 2-approximation algorithm.
Proof. Here's the algorithm:
Using binary search over the $O(n^2)$-pairwise distances $\{d(u,w) : u, w\in V\}$, find the minimum radius $r$ such that the graph $G_r=(V, E_r)$ is bipartite, where $E_r = E \cup\{(u,w) : d(u, w) > r\}$.
...
1
I wrote an implementation of this algorithm here: https://github.com/geodavic/poly_factor
There is also a public API and a website to test it out. See the README.
Only top voted, non community-wiki answers of a minimum length are eligible