A minor characterization of signed graphs with signed Colin de Verdière parameter at most three
A signed graph is a pair consisting of a graph and a set of odd edges. Let denote its signed Colin de Verdière parameter. Write for the signed complete graph on five vertices with the specified odd-edge pattern, and for the corresponding signed complete graph on four vertices. A -transformation replaces a triangle by a new degree-three vertex adjacent to its vertices, and a -transformation is the reverse operation.
Minor characterization conjecture. A signed graph has if and only if has no minor isomorphic to , , or any signed graph that can be obtained from by a sequence of - and -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 and , 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
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.