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

About 14 years old · traced to

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.

References

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.