A graph minors characterization of signed graphs whose signed Colin de Verdière parameter $\nu$ is two

Abstract

A signed graph is a pair $(G,\Sigma )$, where $G=(V,E)$ is a graph (in which parallel edges are permitted, but loops are not) with $V=\{1,...,n\}$ and $\Sigma \subseteq E$. The edges in $\Sigma$ are called odd and the other edges even. By $S(G,\Sigma )$ we denote the set of all symmetric $n\times n$ matrices $A=[a_{i,j}]$ with $a_{i,j}<0$ if $i$ and $j$ are connected by only even edges, $a_{i,j}>0$ if $i$ and $j$ are connected by only odd edges, $a_{i,j}\in \mathbb{R}$ if $i$ and $j$ are connected by both even and odd edges, $a_{i,j}=0$ if $i\ne j$ and $i$ and $j$ are non-adjacent, and $a_{i,i}\in \mathbb{R}$ for all vertices $i$. The parameter $\nu (G,\Sigma )$ of a signed graph $(G,\Sigma )$ is the largest nullity of any positive semidefinite matrix $A\in S(G,\Sigma )$ that has the Strong Arnold Property. By $K_3^{=}$ we denote the signed graph obtained from $(K_3,\varnothing )$ by adding to each even edge an odd edge in parallel. In this paper, we prove that a signed graph $(G,\Sigma )$ has $\nu (G,\Sigma )\le 2$ if and only if $(G,\Sigma )$ has no minor isomorphic to $(K_4,E(K_4))$ or $K_3^{=}$.

15 pages, 2 figures