Article ID Journal Published Year Pages File Type
9512186 Discrete Mathematics 2005 11 Pages PDF
Abstract
We prove that a connected cographic matroid of a graph G is the bias matroid of a signed graph Σ iff G imbeds in the projective plane. In the case that G is nonplanar, we also show that Σ must be the projective-planar dual signed graph of an actual imbedding of G in the projective plane. As a corollary we get that, if G1,…,G29 denote the 29 nonseparable forbidden minors for projective-planar graphs, then the cographic matroids of G1,…,G29 are among the forbidden minors for the class of bias matroids of signed graphs. We will obtain other structural results about bias matroids of signed graphs along the way.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,