Homomorphisms of planar signed graphs to signed projective cubes

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 2g1. 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.

Keywords

• homomorphism
• planar signed graph
• projective cube
• signed graph
• [info.info-dm] computer science [cs]/discrete mathematics [cs.dm]