  A signed bipartite (simple) graph $(G, \sigma)$ is said to be
$C_{-4}$-critical if it admits no homomorphism to $C_{-4}$ (a negative 4-cycle)
but every proper subgraph of it does. In this work, first of all we show that
the notion of 4-coloring of graphs and signed graphs is captured, through
simple graph operations, by the notion of homomorphism to $C_{-4}$. In
particular, the 4-color theorem is equivalent to: Given a planar graph $G$, the
signed bipartite graph obtained from $G$ by replacing each edge with a negative
path of length 2 maps to $C_{-4}$.
  We prove that, except for one particular signed bipartite graph on 7 vertices
and 9 edges, any $C_{-4}$-critical signed graph on $n$ vertices must have at
least $\lceil\frac{4n}{3}\rceil$ edges, and that this bound or
$\lceil\frac{4n}{3}\rceil+1$ is attained for each value of $n\geq 9$. As an
application, we conclude that all signed bipartite planar graphs of negative
girth at least $8$ map to $C_{-4}$. Furthermore, we show that there exists an
example of a signed bipartite planar graph of girth $6$ which does not map to
$C_{-4}$, showing $8$ is the best possible and disproving a conjecture of
Naserasr, Rollova and Sopena, in extension of the above mentioned restatement
of the 4CT.
