Discrete Mathematics & Theoretical Computer Science, Vol 15, No 3 (2013)

Font Size:  Small  Medium  Large

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