Vertex-minors of graphs: A survey

Abstract

For a vertex v of a graph, the local complementation at v is an operation that replaces the neighborhood of v by its complement graph. Two graphs are locally equivalent if one is obtained from the other by a sequence of local complementations. A graph H is a vertex-minor of a graph G if H is an induced subgraph of a graph locally equivalent to G. Although this concept was introduced in the 1980s, it was not widely known and except for the survey paper of Bouchet published in 1990, there is no comprehensive survey listing all the new developments. We survey classic and recent theorems and conjectures on vertex-minors and related concepts such as circle graphs, cut-rank functions, rank-width, and interlace polynomials. © 2024 Elsevier B.V.