Homomorphisms of planar signed graphs to signed projective cubes
Reza Naserasr, Edita Rollová, Éric Sopena
Abstract
We conjecture that every signed graph of unbalanced girth
2g, whose underlying graph is bipartite and planar,
admits a homomorphism to the signed projective cube of dimension
2g-1. Our main result is to show that for a given
g, this conjecture is equivalent to the corresponding
case (k=2g) of a conjecture of Seymour claiming that
every planar k-regular multigraph with no odd
edge-cut of less than k edges is
k-edge-colorable. To this end, we exhibit several
properties of signed projective cubes and establish a folding lemma
for planar even signed graphs.
Full Text: PDF PostScript