A Colin de Verdiere-Type Invariant and Odd-K_4- and Odd-K^2_3-Free Signed Graphs

Abstract

We introduced a new Colin de Verdiere-type invariant \nu(G,\Sigma) for signed graphs. This invariant is closed under taking minors, and characterizes bipartite signed graphs as those signed graphs (G,\Sigma) with \nu(G,\Sigma)\leq 1, and signed graphs with no odd-K_4- and no odd-K^2_3-minor as those signed graphs (G,\Sigma) with \nu(G,\Sigma)\leq 2. In this talk we will discuss this invariant and these results. Joint work with Marina Arav, Frank Hall, and Zhongshan Li.