A minor characterization of signed graphs with signed Colin de Verdière parameter at most three
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.
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.