A minor characterization of signed graphs with signed Colin de Verdière parameter at most three

A signed graph is a pair (G,Σ)(G,\Sigma) consisting of a graph GG and a set Σ\Sigma of odd edges. Let ν(G,Σ)\nu(G,\Sigma) denote its signed Colin de Verdière parameter. Write K5oK_5^o for the signed complete graph on five vertices with the specified odd-edge pattern, and K4=K_4^= for the corresponding signed complete graph on four vertices. A ΔY\Delta Y-transformation replaces a triangle by a new degree-three vertex adjacent to its vertices, and a YΔY\Delta-transformation is the reverse operation.

Minor characterization conjecture. A signed graph (G,Σ)(G,\Sigma) has ν(G,Σ)3\nu(G,\Sigma)\leq 3 if and only if (G,Σ)(G,\Sigma) has no minor isomorphic to K5oK_5^o, K4=K_4^=, or any signed graph (H,Ω)(H,\Omega) that can be obtained from K4=K_4^= by a sequence of ΔY\Delta Y- and YΔY\Delta-transformations.

This conjecture seeks the next excluded-minor characterization for the signed Colin de Verdière parameter after the established characterization for parameter at most two. The paper notes that ν(K5o)=4\nu(K_5^o)=4 and ν(K4=)=4\nu(K_4^=)=4, and that the parameter remains four under the indicated transformations; the proposed characterization is otherwise unresolved in the supplied text.

Sources & referencesView supporting material

Primary source

Marina Arav, Frank J. Hall, Zhongshan Li and Hein van der Holst, “A graph minors characterization of signed graphs whose signed Colin de Verdière parameter ν is two”, arXiv:1209.4628 (2012).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.