# Density of $3$-critical signed graphs

Laurent Beaudou$\,{}^{a}$, Penny Haxell$\,{}^{b}$, Kathryn Nurse$\,{}^{c}$
Sagnik Sen$\,{}^{d}$, and Zhouningxin Wang$\,{}^{e}$

$(a)$ Université Clermont Auvergne, France
$(b)$ University of Waterloo, Waterloo ON, Canada
$(c)$ Simon Fraser University, Burnaby, Canada
$(d)$ Indian Institute of Technology Dharwad, India
$(e)$ School of Mathematical Sciences and LPMC, Nankai University, Tianjin,
China
Emails<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

We say that a signed graph is _$k$ -critical_ if it is not $k$-colorable but
every one of its proper subgraphs is $k$-colorable. Using the definition of
colorability due to Naserasr, Wang, and Zhu [20] that extends the notion of
circular colorability, we prove that every $3$-critical signed graph on $n$
vertices has at least $\frac{3n-1}{2}$ edges, and that this bound is
asymptotically tight. It follows that every signed planar or projective-planar
graph of girth at least $6$ is (circular) $3$-colorable, and for the
projective-planar case, this girth condition is best possible. To prove our
main result, we reformulate it in terms of the existence of a homomorphism to
the signed graph $C_{3}^{*}$, which is the positive triangle augmented with a
negative loop on each vertex.

Keywords: Homomorphism, critical signed graphs, edge-density, circular
coloring.

##  1 Introduction

For a graph property $P$, we say that a graph $G$ is _critical_ for $P$ if
every proper subgraph of $G$ satisfies $P$ but $G$ itself does not. Thus in
particular, every graph that is not $k$-colorable contains a critical subgraph
for $k$-colorability, and hence the study of critical graphs for coloring has
been of key importance in the study of chromatic numbers.

In 2014, Kostochka and Yancey [10, 11] proved the following precise lower
bound on the density of graphs that are critical for $3$-colorability. Note
that the term _$4$ -critical_ is used instead of “critical for
$3$-colorability” in [10, 11] but we avoid it here for consistency.

######  Theorem 1.1.

[10, 11] If a graph $G$ is critical for $3$-colorability, then
$|E(G)|\geq\frac{5|V(G)|-2}{3}$.

Their short proof of this theorem in [11], coupled with a standard argument
about the density of planar graphs, provided a new and elegant proof of the
classical theorem of Grötzsch that every triangle-free planar graph is
$3$-colorable. In addition, Theorem 1.1 resolved the first open case of a
well-known and decades-old conjecture of Ore [21] on the density of critical
graphs for $k$-colorability for every $k$. In [10], Kostochka and Yancey
proved a corresponding density bound for general $k$, thus solving Ore’s
Conjecture exactly or almost exactly in every case.

Our aim in this paper is to address the analogous density question in the
setting of signed graphs. A _signed graph_ $(G,\sigma)$ is a graph $G$
together with a signature $\sigma:E(G)\to\\{+,-\\}$. Thus a graph $G$ can be
regarded as a signed graph $(G,+)$ with all edges being positive (i.e.,
assigned with $+$). One of the main notions distinguishing signed graphs from
$2$-edge-colored graphs (whose edges are simply partitioned into two distinct
types) is the operation of vertex switching. A _switching_ at a vertex $v$ of
a signed graph corresponds to multiplying the signs of all (non-loop) edges
incident to $v$ by $-$. Thus the sign of a loop is invariant under switching.
Two signed graphs are said to be _switching equivalent_ if one can be obtained
from the other by a sequence of vertex switchings. Accordingly, meaningful
parameters of signed graphs should be invariant under vertex switching.

In the seminal paper [25], Zaslavsky introduced a natural definition of
coloring of signed graphs with an even number of colors, half of which are
positive, the other half negative. This notion has been extended to odd
numbers by Máčajová, Raspaud, and Škoviera [14] by introducing the color 0,
which has a special status, and in a different and more symmetric way by
Naserasr, Wang, and Zhu [20] who generalized the definition of circular
coloring of graphs to the case of signed graphs. In this paper, we use the
latter definition, which we now describe.

In the graph setting, a _circular $\frac{p}{q}$-coloring_ of a graph $G$ is a
mapping $f:V(G)\to\\{0,1,\ldots,p-1\\}$ such that for each edge $uv$,
$q\leq|f(u)-f(v)|\leq p-q$. We can think of this as assigning to each vertex a
color chosen from a circular arrangement of $p$ colors, such that adjacent
vertices receive colors that are at distance at least $q$ on the circle. This
well-studied concept refines the usual definition of coloring, coinciding with
the definition of $k$-coloring when $k=\frac{p}{q}$ is an integer. For signed
graphs, given positive integers $p,q$ with $p\geq 2q$ and with $p$ even, a
_circular $\frac{p}{q}$-coloring_ of a signed graph $(G,\sigma)$ is a mapping
$\varphi:V(G)\to\\{0,1,\ldots,p-1\\}$ such that

  * •

for each positive edge $uv$, $q\leq|\varphi(u)-\varphi(v)|\leq p-q$ and

  * •

for each negative edge $uv$, either $|\varphi(u)-\varphi(v)|\leq\frac{p}{2}-q$
or $|\varphi(u)-\varphi(v)|\geq\frac{p}{2}+q$.

Intuitively, vertices adjacent via a positive edge should have colors at
distance at least $q$ on the $p$-cycle of colors as in the graph case, while
for vertices $u$ and $v$ adjacent via a negative edge, the color of $u$ should
be at distance at least $q$ from the _antipodal color_
$\frac{p}{2}+\varphi(v)\pmod{p}$ of $v$. The _circular chromatic number_ of
$(G,\sigma)$ is defined to be

$\chi_{c}(G,\sigma)=\min\Big{\\{}\frac{p}{q}\mid(G,\sigma)\text{ admits a
circular $\frac{p}{q}$-coloring}\Big{\\}}.$

It is not difficult to see that these definitions are invariant under vertex
switching. The notion of criticality then extends in a natural way, and in
particular, we say that a signed graph $(G,\sigma)$ is _(circular)
$3$-critical_ if $\chi_{c}(G,\sigma)>3$ but $\chi_{c}(H,\sigma)\leq 3$ for
every proper subgraph $H$ of $G$.

Our main result gives a signed graphs analogue of Theorem 1.1.

######  Theorem 1.2.

If $(G,\sigma)$ is a signed graph that is (circular) 3-critical, then

$|E(G)|\geq\frac{3|V(G)|-1}{2}.$

Moreover, we show in Section 4 that there is an infinite sequence of such
signed graphs whose edge density is precisely $\frac{3}{2}$. Hence our density
bound is asymptotically tight.

One essentially immediate corollary of Theorem 1.2 is the following result
(see Subsection 1.1), which is analogous to the simple derivation of
Grötzsch’s theorem from Theorem 1.1.

######  Corollary 1.3.

Let $G$ be a planar or projective-planar graph of girth at least $6$. Then for
every signature $\sigma$ on $G$, the signed graph $(G,\sigma)$ is (circular)
$3$-colorable.

We show in Section 4 that this girth bound is best possible for the class of
signed projective-planar graphs. For the planar case, it improves the previous
best known bound of $7$, proved in [18], but at present, we do not know
whether the bound of $6$ is tight. Constructions given in [20, 9] show that
the correct bound cannot be smaller than $5$.

#### Homomorphisms.

In fact, it will be more natural for us to formulate and prove Theorem 1.2 in
terms of homomorphisms. Recall that in the graph setting, a _homomorphism_ of
a graph $G$ to a graph $H$ is a vertex mapping $\varphi:V(G)\to V(H)$ such
that adjacency is preserved. This is a generalization of the definition of
coloring, for example, any proper vertex $k$-coloring of $G$ can be viewed as
a homomorphism of $G$ to the complete graph $K_{k}$, and it is well known that
a graph admits a circular $\frac{2k+1}{k}$-coloring if and only if it admits a
homomorphism to the odd cycle $C_{2k+1}$. For a given graph $H$, a graph $G$
is called _$H$ -critical_ if $G$ does not admit a homomorphism to $H$, but
every proper subgraph of $G$ does.

The definition of homomorphism extends to signed graphs $(G,\sigma)$ as
follows. For a closed walk $W$ in $G$, the _sign_ of $W$ is the product of the
signs of all the edges in $W$ (allowing repetition). A _homomorphism_ of
$(G,\sigma)$ to another signed graph $(H,\pi)$ is a mapping of $V(G)$ to
$V(H)$ such that both the adjacency and the signs of all closed walks are
preserved. If there exists a homomorphism of $(G,\sigma)$ to $(H,\pi)$, then
we write $(G,\sigma)\to(H,\pi)$. Again it is easy to see that the existence of
a homomorphism is invariant under switching. The definition of criticality
also extends in the natural way: given a signed graph $(H,\pi)$, a signed
graph $(G,\sigma)$ is said to be _$(H,\pi)$ -critical_ if $(G,\sigma)$ does
not admit a homomorphism to $(H,\pi)$, but every proper subgraph of
$(G,\sigma)$ does. (More accurately, with certain girth conditions, see
Definition 2.4.)

Our main interest in this paper is in (circular) $3$-coloring of signed
graphs, which by definition is the case $\ell=3$ of circular
$\frac{2\ell}{\ell-1}$-coloring. This sequence of rationals turns out to be of
special interest and importance, in that (analogously to the graph case) it is
closely related to the existence of homomorphisms of signed graphs to signed
cycles. We write $C^{*}_{\ell}$ for a signed cycle of length $\ell$ with an
odd number of positive edges, together with negative loops at each vertex, see
Figure 1. (Note that for fixed $\ell$, all such cycles are switching-
equivalent.)

(a) $C^{*}_{2}$

(b) $C^{*}_{3}$

(c) $C^{*}_{4}$

(d) $C^{*}_{5}$

Figure 1: Signed graphs $C^{*}_{\ell}$. Solid blue edges are positive, dashed
red edges are negative.

The following fact from [19] gives a characterization of circular
$\frac{2\ell}{\ell-1}$-colorable signed graphs in terms of homomorphisms.

######  Proposition 1.4.

[19] A signed graph admits a circular $\frac{2\ell}{\ell-1}$-coloring if and
only if it admits a homomorphism to $C^{*}_{\ell}$.

Proposition 1.4 implies the reformulation of Theorem 1.2 that will be our main
focus from now on.

######  Theorem 1.5.

Every $C^{*}_{3}$-critical signed graph $(G,\sigma)$ satisfies
$|E(G)|\geq\frac{3|V(G)|-1}{2}$.

The rest of the paper is organized as follows. In the next subsection, we give
the (simple) proof of Corollary 1.3, and also outline how our main results
relate to other previous work on graphs and signed graphs. While this material
is not essential to the understanding of this paper, it provides further
motivation and places our results in a broader context. In Section 2, we give
preliminary background on signed graphs and homomorphisms of signed graphs. In
particular, in Section 2.1, we provide some basic properties of
$C^{*}_{3}$-critical signed graphs. In Section 3, we use the potential method
employed in [10], adapted to our setting, to find more forbidden
configurations in the minimum counterexample of our main theorem (Theorem 1.5)
and use the discharging technique to complete the proof. In Section 4, we show
that the edge density bound of Theorem 1.5 is asymptotically tight, and the
girth bound of Corollary 1.3 for the class of signed projective-planar graphs
is tight. We also pose some open questions there.

###  1.1 Further Context

As previously noted, results such as Theorem 1.1 and Theorem 1.5 have direct
implications for colorings (or more generally homomorphisms) of graphs whose
densities are bounded above, for example, graphs embedded on surfaces or
graphs with large girth. We see this explicitly in the following proof of
Corollary 1.3.

Proof of Corollary 1.3. Let ${G=(V,E)}$ be a planar or projective-planar graph
of girth at least $6$, and $\sigma$ be a signature on $G$. If $(G,\sigma)$ is
not $3$-colorable, then by Proposition 1.4 we may assume without loss of
generality that it is $C_{3}^{*}$-critical. Consider a plane or projective-
plane embedding of $G$, and let its set of faces be denoted by $F$. Euler’s
formula states that $|V|-|E|+|F|=2-g$ where $g$ is the genus of the surface in
which the graph is embedded ($0$ for the plane and $1$ for the projective
plane). The girth condition applied to the embedding gives that $|E|\geq
3|F|$. Hence we obtain that $|E|\leq\frac{3|V|-3(2-g)}{2}$, which contradicts
Theorem 1.5. $\Box$

In classical graph theory, one major motivation for proving lower bounds on
the density of critical graphs was Jaeger’s famous Circular Flow Conjecture
[6, 7], which was recently disproved for $k\geq 3$ by Han, Li, Wu, and Zhang
[5]. However, its planar restriction remains open and can be stated as
follows.

######  Conjecture 1.6.

[6] For any integer $k\geq 1$, every planar graph of girth at least $4k$
admits a homomorphism to $C_{2k+1}$.

For general $k$, the best result is due to Lovász, Thomassen, Wu, and Zhang
[13], that the girth condition $6k$ is sufficient. For small values of $k$,
tighter results are known. The case $k=1$ is simply Grötzsch’s theorem [4];
for $k=2$, it has been verified by Dvořák and Postle [3] for the girth
condition $10$; for $k=3$, the best-known girth bound of $16$ has very
recently been achieved by Postle and Smith-Roberge [22]. The same results for
$k=2,3$ were independently obtained by Cranston and Li [2] using the notion of
flows. The results of [3] and [22] are each proved by establishing lower
bounds on the density of $C_{2k+1}$-critical graphs, as follows.

######  Theorem 1.7.

[3] Every $C_{5}$-critical graph $G$ except $C_{3}$ satisfies
$|E(G)|\geq\frac{5|V(G)|-2}{4}$.

######  Theorem 1.8.

[22] Every $C_{7}$-critical graph $G$ except $C_{3}$ and $C_{5}$ satisfies
$|E(G)|\geq\frac{17|V(G)|-2}{15}$.

The general problem of finding the best possible lower bound on the edge
density of $C_{2k+1}$-critical graphs has been studied extensively in the
literature, and we refer to the two papers above and the references therein.

In the setting of signed graphs, the _girth_ of a signed graph $(G,\sigma)$ is
defined as the length of a shortest cycle in $G$, and its _negative-girth_ as
the length of its shortest negative cycle. Parallel to the graph case, the
following natural questions have been addressed in the literature.

  1. 1.

What is the edge density of $C_{\ell}^{*}$-critical signed graphs?

  2. 2.

What is the smallest integer $f(\ell)$ such that every signed planar graph of
girth at least $f(\ell)$ admits a homomorphism to $C_{\ell}^{*}$?

Naserasr, Wang, and Zhu [20] have proved that every signed planar graph of
girth at least $4$ admits a homomorphism to $C^{*}_{2}$, and the girth bound
is best possible due to a result of Kardoš and Narboni [8]. Moreover, by
Proposition 1.4, the circular chromatic number bound $4$ of such signed graphs
is asymptotically tight, as there is a sequence of signed bipartite planar
simple graphs whose circular chromatic number is approaching $4$ [9].
Regarding negative cycles as homomorphism targets, the signed cycle of length
$\ell$ with an odd number of negative edges, written $C_{-\ell}$, has also
been studied. For $\ell=4$, when restricted to bipartite graphs, the following
results have been established.

######  Theorem 1.9.

[15]

  * •

Every $C_{-4}$-critical signed graph $(G,\sigma)$ except one signed graph on
$7$ vertices and with $9$ edges satisfies that $|E(G)|\geq\frac{4|V(G)|}{3}$.

  * •

Every signed bipartite planar graph of negative-girth at least $8$ admits a
homomorphism to $C_{-4}$. Moreover, the negative-girth bound is the best
possible.

Thus our Theorem 1.5 and Corollary 1.3 further contribute to this line of
investigation. In particular, Corollary 1.3 can be viewed as addressing the
most basic case of a signed graph analogue of Conjecture 1.6.

##  2 Preliminaries

In this paper, all graphs are finite and may have multiple edges or loops. If
the signature of a signed graph $(G,\sigma)$ is understood from the context,
or its particular knowledge is irrelevant, we use the simplified notation
$\hat{G}$ to denote it. We denote the _underlying graph_ of a signed graph
$\hat{G}=(G,\sigma)$ by $G$. For the figures, we use a blue solid line to
represent a positive edge, a red dashed line to represent a negative edge, and
a gray line to represent an unsigned edge. A _digon_ is two parallel edges
with different signs. We say $(H,\pi)$ is a _subgraph_ of $(G,\sigma)$ if $H$
is a subgraph of $G$ and $\pi=\sigma|_{H}$.

We use $v(G)$ to denote the number of vertices of $G$ and $e(G)$ to denote the
number of edges of $G$. We say a vertex is a _distance-two neighbor_ of
another vertex if they are connected by a path of length $2$ whose internal
vertex is of degree $2$.

A _$k$ -vertex_ is a vertex having degree $k$ and a _$k^{+}$ -vertex_ is a
vertex of degree at least $k$. A _$k_{\geq\ell}$ -vertex_ (or, _$k_{\leq\ell}$
-vertex_) is a $k$-vertex with at least (respectively, at most) $\ell$
neighbors of degree $2$ and a _$k_{\ell}$ -vertex_ is a $k$-vertex with
exactly $\ell$ neighbors of degree $2$. Other standard notions follow [23].

### Homomorphisms of signed graphs

Switching a subset $S$ of vertices of $(G,\sigma)$ amounts to toggling the
sign of all the edges of the edge-cut $[S,V(G)\setminus S]$. Two signed graphs
$(G,\sigma)$ and $(G,\sigma^{\prime})$, or alternatively, the two signatures
$\sigma$ and $\sigma^{\prime}$ on $G$, are switching equivalent if we can
obtain $(G,\sigma^{\prime})$ from $(G,\sigma)$ by switching at an edge-cut.
Note that switching at an edge-cut does not change the signs of any closed
walk (or cycle). One of the earliest results [24] proved in the theory of
signed graphs characterizes equivalent signed graphs using the sign of their
cycles (or closed walks).

######  Lemma 2.1.

[24] Two signed graphs $(G,\sigma)$ and $(G,\sigma^{\prime})$ are switching
equivalent if and only if each cycle has the same sign in both signed graphs.

Recall that a homomorphism of $(G,\sigma)$ to $(H,\pi)$ is a mapping
$f:V(G)\to V(H)$ such that the adjacency and the signs of closed walks are
preserved. A homomorphism of $(G,\sigma)$ to $(H,\pi)$ is said to be _edge-
sign preserving_ if, furthermore, it preserves the signs of edges.

######  Proposition 2.2.

[16] A signed graph $(G,\sigma)$ admits a homomorphism to $(H,\pi)$ if and
only if there exists a switching-equivalent signature $\sigma^{\prime}$ such
that $(G,\sigma^{\prime})$ admits an edge-sign preserving homomorphism to
$(H,\pi)$.

We have noted before that based on the sign of the cycles and the parity of
their lengths, there are four types of closed walks in signed graphs: positive
odd closed walk (type $01$), negative odd closed walk (type $11$), positive
even closed walk (type $00$) and negative even closed walk (type $10$). We
denote by $g_{{}_{ij}}(G,\sigma)$ for $ij\in\mathbb{Z}^{2}_{2}$ the length of
a shortest closed walk of type $ij$ in a signed graph $(G,\sigma)$. The next
lemma provides a necessary condition for a signed graph to admit a
homomorphism to another.

######  Lemma 2.3.

[17] If $(G,\sigma)\to(H,\pi)$, then $g_{{}_{ij}}(G,\sigma)\geq
g_{{}_{ij}}(H,\pi)$ for $ij\in\mathbb{Z}^{2}_{2}$.

It is easy to observe that if a signed graph $(G,\sigma)$ is
$(H,\pi)$-critical and there exists $ij\in\mathbb{Z}^{2}_{2}$ such that
$g_{{}_{ij}}(G,\sigma)\leq g_{{}_{ij}}(H,\pi)$, then $(G,\sigma)$ is just a
signed cycle of type $ij$. To eliminate the trivial case, we use the notion of
$(H,\pi)$-critical signed graph defined as follows:

######  Definition 2.4.

[15] A signed graph $\hat{G}$ is _$\hat{H}$ -critical_ if for
$ij\in\mathbb{Z}^{2}_{2}$, $g_{{}_{ij}}(\hat{G})\geq g_{{}_{ij}}(\hat{H})$,
$\hat{G}$ admits no homomorphism to $\hat{H}$ but any proper subgraph of
$\hat{G}$ does.

In particular, this means any $C^{*}_{3}$-critical signed graph has no digon
and no positive loop.

### Circular colorings of signed graphs

The notion of the circular coloring of signed graphs is a refinement of both
the notions of $0$-free colorings of signed graphs and circular colorings of
simple graphs. Now we are going to show how homomorphism captures the notion
of circular $\frac{p}{q}$-coloring of signed graphs for any rational number
$\frac{p}{q}$. To do so, we need a special family of signed graphs.

######  Definition 2.5.

[20] Given two positive integers $p$ and $q$ with $p$ being even, the
_circular $\frac{p}{q}$-clique_, denoted $K^{s}_{p;q}$, is a signed graph
having the set of vertices $\\{0,1,\cdots,p-1\\}$, and edges and signature as
follows: (1) $ij$ is a positive edge if $q\leq|i-j|\leq p-q$, (2) $ij$ is a
negative edge if either $|i-j|\leq\frac{p}{2}-q$ or $|i-j|\geq\frac{p}{2}+q$.

The signed graph $K^{s}_{p;q}$ contains a negative loop at each vertex, and,
moreover, it contains a digon if and only if $\frac{p}{q}\geq 4$.

Note that in $K^{s}_{p;q}$, each vertex $i$ and its antipodal vertex
$\bar{i}=i+\frac{p}{2}$ (taken modulo $p$) has exactly an opposite
neighborhood, that is to say, a vertex is adjacent to $i$ by a positive edge
while it is adjacent to $\bar{i}$ by a negative edge. We may switch at
$\\{\frac{p}{2},\ldots,p-1\\}$ and identify each of them with their antipodes,
and the resulting signed graph is denoted by $\hat{K}^{s}_{p;q}$. Such
$\hat{K}^{s}_{p;q}$ has exactly $\frac{p}{2}$ vertices.

Given any positive rational number $\frac{p}{q}$, the circular
$\frac{p}{q}$-clique $K^{s}_{p;q}$ and its switching core $\hat{K}^{s}_{p;q}$
are put into our context in the following proposition.

######  Proposition 2.6.

[20] Given a signed graph $(G,\sigma)$, the following statements are
equivalent:

  * •

$(G,\sigma)$ admits a circular $\frac{p}{q}$-coloring;

  * •

$(G,\sigma)$ admits an edge-sign preserving homomorphism to $K^{s}_{p;q}$;

  * •

$(G,\sigma)$ admits a homomorphism to $\hat{K}^{s}_{p;q}$.

We note that $\hat{K}^{s}_{2\ell;\ell-1}$ is switching isomorphic to
$C^{*}_{\ell}$.

###  2.1 Properties of $C_{3}^{*}$-critical signed graphs

We say a triangle is a graph that is a cycle $C_{3}$ of length three. We
denote by $C_{3}^{*}$ the signed graph in Figure 3 which is a positive
triangle with a negative loop at each vertex.

Recall that a signed graph $\hat{G}$ is _$C_{3}^{*}$ -critical_ if the
following three conditions are satisfied: there is no digon or positive loop
in $\hat{G}$, $\hat{G}\not\rightarrow C_{3}^{*}$, and
$\hat{G}^{\prime}\rightarrow C_{3}^{*}$ for any proper subgraph
$\hat{G}^{\prime}\subsetneq\hat{G}$. First we give an example, depicted in
Figure 3, which is $C_{3}^{*}$-critical and satisfies the condition
$e(G)=\frac{3v(G)-1}{2}$.

$x_{\scriptsize 1}$$x_{\scriptsize 2}$$x_{\scriptsize 3}$ Figure 2:
$C^{*}_{3}\equiv\hat{K}^{s}_{6;2}$

$v_{\scriptsize 0}$$v_{\scriptsize 4}$$v_{\scriptsize 1}$$v_{\scriptsize
2}$$v_{\scriptsize 3}$ Figure 3: $C^{*}_{3}$-critical signed graph $\hat{W}$

######  Lemma 2.7.

The signed graph $\hat{W}$ is $C_{3}^{*}$-critical.

###### Proof.

Suppose for contradiction that $\hat{W}\to C_{3}^{*}$. By Proposition 2.2,
there is a switching-equivalent signature $\sigma^{\prime}$ of $\hat{W}$ such
that $(W,\sigma^{\prime})$ admits an edge-sign preserving homomorphism to
$C^{*}_{3}$. We first observe that under $\sigma^{\prime}$ any negative
$4$-cycle contains only one negative edge and any positive cycle contains no
negative edges. Subject to these two conditions, $\sigma^{\prime}$ is unique
as drawn in Figure 3. Hence, by examining the subgraph $\hat{W}-v_{4}$, in any
edge-sign preserving homomorphism $\varphi$ of $(W,\sigma^{\prime})$ to
$C^{*}_{3}$, $\varphi(v_{1})=\varphi(v_{2})$. But then together with
$\varphi(v_{4})$, it would form a digon, which does not exist in $C^{*}_{3}$,
a contradiction. Therefore, $\hat{W}\not\to C_{3}^{*}$. Finally, it is easy to
see that any proper subgraph of $\hat{W}$ admits a homomorphism to
$C^{*}_{3}$. Thus $\hat{W}$ is $C^{*}_{3}$-critical. ∎

In the arguments that follow we will employ a general technique to “color” a
signed graph $\hat{G}$ by extending a “pre-coloring” of its subgraph
$\hat{H}$. First, we assume that there exists an edge-sign preserving
homomorphism of $\hat{H}$ to $C_{3}^{*}$ under the signature of $\hat{G}$.
Once we fix the homomorphism of $\hat{H}$ to $C_{3}^{*}$, we never again
switch at the vertices of $\hat{H}$. To extend this homomorphism, we may
switch at the vertices in $V(G)\setminus V(H)$. In this setting, it makes
sense to speak of the sign of a path if both ends of a path are fixed in
$\hat{H}$. The _sign_ of a path is then the product of the signs of all of its
edges. Motivated by this, in the sequel, we use figures with round or square
vertices to denote properties of the coloring and structure: we use a round
vertex to denote a vertex that is not pre-colored, at which we allow
switching, and whose degree is shown in the figure; We use a square vertex to
denote a vertex which is pre-colored, at which we do not allow switching,
which may have neighbors not drawn in the figure, and, moreover, which may not
be distinct from other square vertices.

######  Observation 2.8.

Let $\hat{P}$ be a signed path with the endpoints $x$ and $y$, which contains
at most one negative edge. Let $S_{x},S_{y}\subseteq V(C^{*}_{3})$. Let
$\varphi:\\{x,y\\}\to V(C^{*}_{3})$ be such that $\varphi(x)\in S_{x}$ and
$\varphi(y)\in S_{y}$. The mapping $\varphi$ can be extended to an edge-sign
preserving homomorphism of $\hat{P}$ to $C^{*}_{3}$ unless one of the
following conditions is satisfied:

  1. 1.

$\hat{P}$ is either a positive edge or a negative path of length $2$,
$S_{x}=S_{y}$ and $|S_{x}|=1$;

  2. 2.

$\hat{P}$ is a negative edge and $S_{x}\cap S_{y}=\emptyset$.

To justify this observation, note that when the above conditions are not
satisfied $\hat{P}$ has at least two positive edges, which affords enough
flexibility in the mapping.

A _theta graph_ is a simple graph that is the union of three internally
disjoint paths that have the same two end vertices.

######  Lemma 2.9.

Every signed theta graph $\hat{\Theta}$ admits a homomorphism to $C^{*}_{3}$
and is therefore not $C^{*}_{3}$-critical.

###### Proof.

Among the three paths of a signed theta graph $\hat{\Theta}$, two of them, say
$\hat{P}_{1},\hat{P}_{2}$ with $v(\hat{P}_{1})\geq v(\hat{P}_{2})$, have the
same parity of the number of positive edges. For each negative edge $e=uv$ of
those paths, identify $u$ and $v$. Now it is easy to see that
$\hat{P}_{1}\rightarrow\hat{P}_{2}$. Therefore, $\hat{\Theta}\to C_{3}^{*}$ if
and only if $\hat{\Theta}-E(\hat{P}_{1})\to C_{3}^{*}$. But
$\hat{\Theta}-E(\hat{P}_{1})$ is a signed cycle (which is not a digon), and
therefore admits a homomorphism to $C^{*}_{3}$. ∎

In fact, Lemma 2.9 holds more generally: no signed theta graph $\hat{\Theta}$
is $C^{*}_{\ell}$-critical, and every signed theta graph which does not
violate the girth conditions admits a homomorphism to $C^{*}_{\ell}$.

######  Lemma 2.10.

No $C_{3}^{*}$-critical signed graph contains an edge of the following type:
loop-edge, parallel-edge, or cut-edge.

###### Proof.

Let $\hat{G}$ be a $C_{3}^{*}$-critical signed graph, and let $e\in
E(\hat{G})$. By definition of criticality, $\hat{G}\not\to C_{3}^{*}$ but
$\hat{G}-e\to C_{3}^{*}$. We will show, in order, that $e$ cannot be a type of
edge listed in the lemma.

First, suppose $e$ is a loop. The signed graph $C_{3}^{*}$ has
$g_{{}_{01}}(C_{3}^{*})=3$, and so $e$ must be a negative loop. Since
$C_{3}^{*}$ has negative loops at each vertex, $\hat{G}-e\to C_{3}^{*}$ if and
only if $\hat{G}\to C_{3}^{*}$, a contradiction.

Next, suppose edge $f$ is parallel to $e$. The signed graph $C_{3}^{*}$ has
$g_{{}_{10}}(C_{3}^{*})=4$, which means that $e$ and $f$ must have the same
sign. But since edges $e$ and $f$ have the same endpoints and sign,
$\hat{G}-e\to C_{3}^{*}$ if and only if $\hat{G}\to C_{3}^{*}$, a
contradiction.

Finally, suppose that $e$ is a cut-edge with ends $u$ and $v$. Let
$\hat{G}_{u}$ and $\hat{G}_{v}$ be the components of $\hat{G}-e$ containing
$u$ and $v$ respectively. Since $\hat{G}$ is $C_{3}^{*}$-critical, there exist
homomorphisms $\psi_{1}:\hat{G}_{u}\to C_{3}^{*}$ and $\psi_{2}:\hat{G}_{v}\to
C_{3}^{*}$. By the vertex-transitivity of $C_{3}^{*}$, we may assume
$\psi_{1}(u)=\psi_{2}(v)$ if $e$ is negative and $\psi_{1}(u)\neq\psi_{2}(v)$
if $e$ is positive. But, by Observation 2.8, $\psi_{1}\cup\psi_{2}:\hat{G}\to
C_{3}^{*}$, a contradiction. ∎

######  Lemma 2.11.

No $C_{3}^{*}$-critical signed graph contains a vertex of the following type:
$1$-vertex, $2_{1}$-vertex, $4_{4}$-vertex, or $5_{5}$-vertex.

$v$$v_{3}$$v_{2}$$v_{4}$$v_{1}$ Figure 4: A $4_{4}$-vertex $v$ and its
distance-two neighbors.

###### Proof.

Let $\hat{G}$ be a $C_{3}^{*}$-critical signed graph. Suppose to the contrary
that there is a vertex $v$ in $\hat{G}$ of a type listed in the lemma. By
Lemma 2.10, $v$ cannot be a $1$-vertex.

If $v$ is a $2_{1}$-vertex, let $\hat{G}^{\prime}$ be the signed graph
obtained from $\hat{G}$ by deleting $v$ and its $2$-neighbor. By criticality,
there is a homomorphism $\varphi:\hat{G}^{\prime}\to C_{3}^{*}$. But by
Observation 2.8, $\varphi$ can be extended to a homomorphism of $\hat{G}$ to
$C_{3}^{*}$. This contradicts that $\hat{G}$ is $C_{3}^{*}$-critical.

Suppose $v$ is a $4_{4}$-vertex. Let $v_{1},v_{2},v_{3},v_{4}$ be the
distance-two neighbors of $v$, see Figure 4. Let $\hat{H}$ be the signed graph
obtained from $\hat{G}$ by deleting $v$ and its $2$-neighbors. Since $\hat{H}$
is a proper subgraph of a $C_{3}^{*}$-critical signed graph, there is a
homomorphism $\varphi$ of $\hat{H}$ to $C^{*}_{3}$. Assume that $\varphi$ is
edge-sign preserving under the signature $\sigma$. By possibly switching at
$v$, we may assume that among four $vv_{i}$-paths at most two of them are
negative, say $vv_{1}$-path and $vv_{2}$-path if there exists two. Let
$\varphi(v)\in V(C^{*}_{3})\setminus\\{\varphi(v_{1}),\varphi(v_{2})\\}$. By
Observation 2.8, such a mapping can be extended to those $2$-neighbors of $v$,
a contradiction.

The case when $v$ is a $5_{5}$-vertex is similar to the $4_{4}$-vertex case,
where again we may assume that there are at most two negative paths, and we
omit the proof. ∎

######  Lemma 2.12.

No $C_{3}^{*}$-critical signed graph contains a $3_{2}$-vertex.

$w$$v$$y$$x$ Figure 5: A $3_{2}$-vertex $v$ and surrounding graph.

###### Proof.

Let $\hat{G}$ be a $C_{3}^{*}$-critical signed graph. Suppose to the contrary
that there is a $3_{2}$-vertex $v$ in $\hat{G}$. Let $x$ and $y$ be its
distance-two neighbors, and $w$ be the remaining neighbor of $v$. See Figure
5.

Let $\hat{H}$ be the signed graph obtained from $\hat{G}$ by deleting the
vertex $v$ and its two $2$-neighbors. By the criticality of $\hat{G}$, there
is a homomorphism $\psi:\hat{H}\rightarrow C_{3}^{*}$. We claim that $\psi$
can be extended to a homomorphism of $\hat{G}$ to $C_{3}^{*}$. Assume that
$\sigma$ of $\hat{G}$ is the signature under which $\hat{H}$ admits an edge-
sign preserving homomorphism to $C_{3}^{*}$. By possibly switching at $v$, we
may assume that at most one of the three paths $vw$-path, $vx$-path, and
$vy$-path is negative under $\sigma$. Moreover, we may assume each of the
three paths has at most one negative edge. If none of the three paths are
negative, let $\psi(v)\in V(C_{3}^{*})\setminus\psi(w)$. If $vw$-path is the
sole negative path, let $\psi(v)=\psi(w)$. If, without loss of generality,
$vx$-path is negative, then let $\psi(v)\in
V(C_{3}^{*})\setminus\\{\psi(x),\psi(w)\\}$. In each case, $\psi$ can be
extended to a homomorphism from $G$ to $C_{3}^{*}$ by Observation 2.8. ∎

######  Lemma 2.13.

Let $\hat{T}$ be a signed triangle with vertex set $\\{v_{1},v_{2},v_{3}\\}$
and contains at most one negative edge. Let $S_{i}\subseteq V(C^{*}_{3})$ for
$i\in\\{1,2,3\\}$. There exists an edge-sign preserving homomorphism
$\varphi:V(\hat{T})\to V(C^{*}_{3})$ such that $\varphi(v_{i})\in S_{i}$ for
each $i\in\\{1,2,3\\}$ if one of the following conditions are satisfied:

  1. (1)

$|S_{1}|\geq 2,|S_{2}|\geq 2,$ and $|S_{3}|=3$;

  2. (2)

$|S_{1}|\geq 1,|S_{2}|=3,$ and $|S_{3}|=3$;

  3. (3)

$|S_{1}|\geq 1,|S_{2}|\geq 2,|S_{3}|=3,$ and $v_{1}v_{2}$ is not the negative
edge if $\hat{T}$ is negative;

  4. (4)

$|S_{1}|=|S_{2}|=|S_{3}|=2$, and $S_{2}\cup S_{3}=V(C_{3}^{*})$.

###### Proof.

For Cases (1) and (2), the argument is the same. In both cases, if $\hat{T}$
contains three positive edges, then we can choose $\varphi(v_{1})\in S_{1}$,
$\varphi(v_{2})\in S_{2}\setminus\\{\varphi(v_{1})\\}$ and $\varphi(v_{3})\in
S_{3}\setminus\\{\varphi(v_{1}),\varphi(v_{2})\\}$ in this order. If $\hat{T}$
contains one negative edge $v_{i}v_{j}$, then we choose
$\varphi(v_{i})=\varphi(v_{j})\in S_{i}\cap S_{j}$ and then for
$k\in\\{1,2,3\\}\setminus\\{i,j\\}$, $\varphi(v_{k})\in
S_{k}\setminus\\{\varphi(v_{i})\\}$. Just be careful in Case (2), if the only
negative edge is $v_{2}v_{3}$, then we can always choose
$\varphi(v_{2})=\varphi(v_{3})\in S_{2}\cap S_{3}\setminus S_{1}$ to guarantee
that $S_{1}\setminus\\{\varphi(v_{2})\\}$ is not empty.

For Case (3), if $\hat{T}$ is positive, then the same argument above works. If
$v_{2}v_{3}$ is the only negative edge, then we choose
$\varphi(v_{2})=\varphi(v_{3})\in S_{2}\cap S_{3}\setminus S_{1}$ and choose
$\varphi(v_{1})\in S_{1}$; if $v_{1}v_{3}$ is the only negative edge, then we
choose $\varphi(v_{1})=\varphi(v_{3})\in S_{1}$ and set $\varphi(v_{2})\in
S_{2}\setminus S_{1}$.

For Case (4), if $\hat{T}$ is negative then the argument for Case (1) works.
Otherwise $\hat{T}$ is positive and we may choose $\varphi(v_{1})\in S_{1}$.
Because $S_{2}\cup S_{3}=V(C_{3}^{*})$, it follows that
$S_{2}\setminus\\{\varphi(v_{1})\\}\neq S_{3}\setminus\\{\varphi(v_{1})\\}$.
Hence we may choose $\varphi(v_{2})\in S_{2}\setminus\\{\varphi(v_{1})\\}$ and
$\varphi(v_{3})\in S_{3}\setminus\\{\varphi(v_{1})\\}$ so that
$\varphi(v_{2})\neq\varphi(v_{3})$. ∎

######  Lemma 2.14.

No signed triangle $\hat{T}$ of the following type is contained in a
$C_{3}^{*}$-critical signed graph:

  1. (i)

two $3_{1}$-vertices and a $5_{3}$-vertex;

  2. (ii)

a $3_{1}$-vertex and two $4_{2}$-vertices;

  3. (iii)

a $3_{1}$-vertex, a $3$-vertex, and a $4_{2}$-vertex.

$x_{3}$$x_{4}$$x_{5}$$v_{3}$$v_{1}$$x_{1}$$v_{2}$$x_{2}$(i)$\hat{T}$$x_{3}$$x_{2}$$x_{4}$$x_{5}$$v_{2}$$v_{1}$$x_{1}$$v_{3}$(ii)$\hat{T}$$x_{2}$$x_{3}$$x_{4}$$v_{2}$$v_{1}$$x_{1}$$v_{3}$(iii)$\hat{T}$
Figure 6: The three cases in Lemma 2.14

###### Proof.

Let $\hat{G}$ be a $C_{3}^{*}$-critical signed graph. Let the vertices at
distance at most two from $\hat{T}$ be labeled as in Figure 6. We proceed by
cases. In each case, suppose for contradiction that the described signed
triangle $\hat{T}$ does exist in $\hat{G}$. Let $\mathcal{P}$ denote the set
of paths in $\hat{G}\setminus E(\hat{T})$ drawn in Figure 6 that join $v_{i}$
and $x_{j}$ for some $i,j$. Let $N$ be the internal vertices of the paths of
$\mathcal{P}$. Let $\hat{H}$ denote the signed graph obtained from $\hat{G}$
by deleting $V(T)\cup N$. By the criticality of $\hat{G}$, there is a
homomorphism $\psi:\hat{H}\rightarrow C_{3}^{*}$. Let $\sigma$ be a signature
of $\hat{G}$ such that $(H,\sigma|_{H})$ admits an edge-sign preserving
homomorphism to $C^{*}_{3}$. By possibly switching at some subset of
$V(\hat{T})$, we may assume that there is at most one negative edge in
$\hat{T}$ with respect to $\sigma$.

Cases (i) and (ii). By possibly switching on the set $V(T)$, we may assume at
most two of the five paths in $\mathcal{P}$ are negative under $\sigma$.
Further, by possibly switching on the vertices in $N$, we may assume each path
of $\mathcal{P}$ has at most one negative edge. We proceed in two sub-cases.

First, suppose that there is at most one negative path in $\mathcal{P}$, and
denote the end point of that path in $\hat{T}$ by $v_{k}$ and the other
endpoint by $x_{k}$. We define $S_{k}=V(C_{3}^{*})\setminus\psi(x_{k})$ and
$S_{i}=S_{j}=V(C^{*}_{3})$ for $v_{i},v_{j}\in
V(\hat{T})\setminus\\{v_{k}\\}$. Noting $|S_{k}|=2,|S_{i}|=|S_{j}|=3$, by
Lemma 2.13 (1), we can choose $\psi(v_{\ell})\in S_{\ell}$ for
$\ell\in\\{1,2,3\\}$ such that $\psi:V(\hat{G})\setminus N\to V(C_{3}^{*})$ is
an edge-sign preserving homomorphism of $\hat{G}-N$ to $C^{*}_{3}$. Then by
Observation 2.8, we can extend this homomorphism to the remaining vertices of
$\hat{G}$.

Second, if exactly two paths are negative, then let $v_{a},v_{b}$ be the ends
of those paths on $T$ and let $x_{i},x_{j}$ be the other ends of these two
paths, respectively. If $v_{a}\neq v_{b}$, then set
$S_{a}=V(C^{*}_{3})\setminus\\{\psi(x_{i})\\}$,
$S_{b}=V(C^{*}_{3})\setminus\\{\psi(x_{j})\\}$ and $S_{k}=V(C^{*}_{3})$ where
$k\in[3]\setminus\\{a,b\\}$. Since $|S_{a}|=|S_{b}|=2$ and $|S_{k}|=3$, by
Lemma 2.13 (1), we can choose $\psi(v_{\ell})\in S_{\ell}$ for
$\ell\in\\{1,2,3\\}$ such that $\psi:V(\hat{G})\setminus N\to V(C_{3}^{*})$ is
an edge-sign preserving homomorphism of $\hat{G}-N$ to $C^{*}_{3}$. Then by
Observation 2.8, we can extend this homomorphism to the remaining vertices of
$\hat{G}$. Similarly, if $v_{a}=v_{b}$, then we set
$S_{a}=V(C^{*}_{3})\setminus\\{\psi(x_{i}),\psi(x_{j})\\}$ and set
$S_{\alpha}=S_{\beta}=V(C^{*}_{3})$ where
$\alpha,\beta\in[3]\setminus\\{a\\}$. Again, by Lemma 2.13 (2) and Observation
2.8 we can extend this homomorphism to the remaining vertices of $\hat{G}$. In
both cases, it is a contradiction as $\hat{G}\rightarrow C_{3}^{*}$.

Case (iii). We may assume $\sigma$ satisfies the following: If $\hat{T}$ has a
negative edge, then it is $v_{1}v_{3}$; At most two of the four paths in
$\mathcal{P}$ are negative; If exactly two such paths are negative, then
$v_{2}x_{2}$ is negative. The first is accomplished by switching on some
subset of $V(\hat{T})$, and the last two by possibly switching on the set
$V(\hat{T})$. As before, we assume each path of $\mathcal{P}$ has at most one
negative edge.

No matter the sign of $v_{2}x_{2}$, there is at most one negative path in
$\mathcal{P}\setminus\\{v_{2}x_{2}\\}$. Let $v_{k}\in\\{v_{1},v_{3}\\}$ so
that $v_{k}$ is an endpoint of the negative path (and $x_{k}$ is the other
end) if it exists. We proceed in two sub-cases based on the sign of
$v_{2}x_{2}$.

If $v_{2}x_{2}$ is positive, then we set
$S_{2}=V(C^{*}_{3})\setminus\\{\psi(x_{2})\\},S_{k}=V(C^{*}_{3})\setminus\\{\psi(x_{k})\\}$
and $S_{\ell}=V(C^{*}_{3})$ where $\ell\in[3]\setminus\\{2,k\\}$. By a similar
argument as above and by Lemma 2.13 (1), we are done.

If $v_{2}x_{2}$ is negative, then we set
$S_{2}=\\{\psi(x_{2})\\},S_{k}=V(C^{*}_{3})\setminus\\{\psi(x_{k})\\}$ and
$S_{\ell}=V(C^{*}_{3})$ where $\ell\in[3]\setminus\\{2,k\\}$. By a similar
argument as above and by Lemma 2.13 (3), we are done. ∎

##  3 Density of $C_{3}^{*}$-critical signed graphs

The _potential_ of a graph $G$ is defined as

$\rho(G)=3v(G)-2e(G).$

The potential of a signed graph is the potential of its underlying graph. We
first give the potential of some simple graphs.

######  Observation 3.1.

We have $\rho(K_{1})=3$, $\rho(K_{2})=4$, $\rho(K_{3})=3$, and
$\rho(K_{4})=0$.

In this section, we shall prove the following alternative formulation of
Theorem 1.5.

######  Theorem 3.2.

If $\hat{G}$ is $C^{*}_{3}$-critical, then $\rho(G)\leq 1$.

To prove it, we assume to the contrary that there exists a
$C^{*}_{3}$-critical signed graph $\hat{G}$ with $\rho(G)\geq 2$ such that
among all such counterexamples to Theorem 3.2 it has the minimum number of
vertices. This means any $C^{*}_{3}$-critical signed graph $\hat{G}^{\prime}$
with $|V(G^{\prime})|<|V(G)|$ satisfies that $\rho(G^{\prime})\leq 1$. We fix
the minimum counterexample $\hat{G}$ for the rest of this section and finally
arrive at a contradiction to prove Theorem 3.2. Initially, we will develop
several structural properties of $\hat{G}$, after which we apply a discharging
argument to force a contradiction.

Given a (signed) graph $\hat{H}$, let $P_{2}(\hat{H})$ denote a graph obtained
from (the underlying graph of) $\hat{H}$ by adding a new $2$-vertex incident
to two new edges whose other ends are distinct vertices in $\hat{H}$. By a
slight abuse of notation, we sometimes treat $P_{2}(\hat{H})$ as a signed
graph.

######  Lemma 3.3.

Let $\hat{H}$ be a subgraph of $\hat{G}$. Then

  1. (i)

$\rho({H})\geq 2$, if $\hat{G}=\hat{H}$;

  2. (ii)

$\rho({H})\geq 3$, if $\hat{G}=P_{2}(\hat{H})$;

  3. (iii)

$\rho({H})=3$, if $H=K_{1}$ or $K_{3}$;

  4. (iv)

$\rho({H})\geq 4$, otherwise.

###### Proof.

It is straightforward to verify (i), (ii), and (iii). Indeed, if
$\hat{H}=\hat{G}$ then the lemma is satisfied by our assumption that
$\rho(G)\geq 2$; if $P_{2}(\hat{H})=\hat{G}$, then $\rho(H)=\rho(G)-3+4\geq
3$; if $H=K_{1}$ or $K_{3}$, then the lemma is satisfied by Observation 3.1.

Suppose for contradiction that (iv) is false. Let $\hat{H}\subseteq\hat{G}$ be
a subgraph which does not satisfy (iv), chosen so that among all such
subgraphs $v(\hat{H})+e(\hat{H})$ is maximum. Note that $\hat{H}\neq\hat{G}$,
$P_{2}(\hat{H})\neq\hat{G}$, $\hat{H}\not\in\\{K_{1},K_{3}\\}$, and
$\rho(\hat{H})\leq 3$. We first claim that $\hat{H}$ is an induced subgraph of
$\hat{G}$. Otherwise, assume that $e\not\in E(\hat{H})$ is an edge connecting
two vertices of $\hat{H}$. Note that $\rho(\hat{H}+e)=\rho(\hat{H})-2\leq
1<\rho(\hat{H})$, and $v(\hat{H}+e)+e(\hat{H}+e)>v(\hat{H})+e(\hat{H})$. By
(i), (ii), and (iii), it follows that $\hat{H}+e\neq\hat{G}$,
$P_{2}(\hat{H}+e)\neq\hat{G}$, $\hat{H}+e\not\in\\{K_{1},K_{3}\\}$. Thus the
existence of $\hat{H}+e$ contradicts the maximality of $\hat{H}$. Therefore,
$\hat{H}$ is an induced subgraph.

By Observation 3.1, we know that $v(\hat{H})\geq 4$. Since $\hat{H}$ is a
proper subgraph of $\hat{G}$ and $\hat{G}$ is $C_{3}^{*}$-critical, there
exists a homomorphism $\psi:\hat{H}\rightarrow C_{3}^{*}$. We may assume that
$\sigma$ is a signature of $\hat{G}$ such that $\psi$ is an edge-sign
preserving homomorphism of $(H,\sigma|_{H})$ to $C_{3}^{*}$. We build a signed
graph $\hat{G}_{1}$ from $\hat{G}$ by identifying any $u,v\in V(\hat{H})$
whenever $\psi(u)=\psi(v)$ and deleting resulting parallel edges of the same
sign so that only one representative remains.

We proceed with four observations about $\hat{G}_{1}$. First, $\hat{G}_{1}$
has no positive loops because $\psi(u)=\psi(v)$ only if $uv$ is not a positive
edge in $\hat{G}$. Second,
$v(\hat{G}_{1})+e(\hat{G}_{1})<v(\hat{G})+e(\hat{G})$ as $v(\hat{H})\geq
4>v(C^{*}_{3})$ which means at least two vertices were identified while
forming $\hat{G}_{1}$. Third, $\hat{G}_{1}\not\rightarrow C_{3}^{*}$ because
otherwise $\hat{G}\rightarrow C_{3}^{*}$ by the transitivity of homomorphisms,
which would contradict that $\hat{G}$ is $C_{3}^{*}$-critical. Fourth and
finally, $\hat{G}_{1}$ has no digon. Suppose to the contrary that there is a
digon in $\hat{G}_{1}$. This means that in $\hat{G}$ there is a negative path
$\hat{P}$ of length $2$ (with respect to the signature $\sigma$) so that the
ends of $\hat{P}$ are in $V(\hat{H})$ while the internal vertex of $\hat{P}$
is in $V(\hat{G}-\hat{H})$. Then $\rho(\hat{P}+\hat{H})=\rho(\hat{H})+3-4\leq
2$. Note that $\hat{P}+\hat{H}$ is also a subgraph of $\hat{G}$ but has more
vertices plus edges than $\hat{H}$ and moreover, $\rho(\hat{P}+\hat{H})\leq
2<\rho(\hat{H})$. By the choice of $\hat{H}$ and claim (i), it must be that
$\hat{G}=\hat{P}+\hat{H}$, contradicting that $\hat{G}\neq P_{2}(\hat{H})$.
Thus $\hat{G}_{1}$ has no digon.

By the first, third, and fourth observations above, $\hat{G}_{1}$ contains a
$C_{3}^{*}$-critical subgraph $\hat{G}_{2}$. Let $X\subseteq V(\hat{G}_{1})$
be the identified vertices of $\hat{H}$ (including trivial identification if
$\psi^{-1}(u)$ is a singleton set for some $u\in V(C^{*}_{3})$). First,
observe that $X\cap V(\hat{G}_{2})\neq\emptyset$ because otherwise
$\hat{G}_{2}\subsetneq\hat{G}$ but both of them are $C_{3}^{*}$-critical.
Also, $V(\hat{G}_{2})\setminus X\neq\emptyset$ because otherwise $\hat{G}_{2}$
is a subgraph of $C^{*}_{3}$ which would mean $\hat{G}_{2}\rightarrow
C_{3}^{*}$, a contradiction. Since $v(\hat{G}_{2})+e(\hat{G}_{2})\leq
v(\hat{G}_{1})+e(\hat{G}_{1})<v(\hat{G})+e(\hat{G})$, by the choice of the
minimum counterexample $\hat{G}$ (to Theorem 3.2), we know that
$\rho(\hat{G}_{2})\leq 1$.

We now construct a signed graph $\hat{G}_{3}$ from the disjoint union of
$\hat{G}_{2}-X$ and $\hat{H}$ by adding the following edges. For each vertex
$v\in V(\hat{G}_{2})\setminus X$ and each vertex $u\in X$, if $vu\in
E(\hat{G}_{2})$, then choose a representative edge $vw\in E(\hat{G})$ for some
$w\in\psi^{-1}(u)$ to be included in $E(\hat{G}_{3})$. In this way,
$\hat{G}_{3}\subseteq\hat{G}$, and because $V(\hat{G}_{2})\setminus
X\neq\emptyset$, $\hat{H}\subsetneq\hat{G}_{3}$.

Now we consider the vertices and edges in $\hat{G_{3}}$. It is straightforward
to see that $V(\hat{G}_{3})=V(\hat{G}_{2})\cup V(\hat{H})\setminus V(X)$, and
so

$v(\hat{G}_{3})=v(\hat{G}_{2})+v(\hat{H})-|X|.$ (1)

An edge of $\hat{G}_{3}$ is of one of three types: (a) edges in
$\hat{G}_{2}\setminus X$; (b) edges in $\hat{H}$; and (c) edges with one end
in $\hat{G}_{2}\setminus X$, and the other end in $\hat{H}$. Similarly, edges
in $\hat{G_{2}}$ have one of three types: (a) edges in $\hat{G}_{2}\setminus
X$; (d) edges with both ends in $X$; and (e) edges with one end in
$\hat{G}_{2}\setminus X$, and the other end in $X$. But, by construction,
there is a one-to-one correspondence between edges of type (c) and (e).
Therefore,

$e(\hat{G}_{3})=e(\hat{G}_{2})+e(\hat{H})-e(G_{2}[X]).$ (2)

Hence, noting $\rho(\hat{G}_{2})\leq 1$, $\rho(\hat{H})\leq 3$, and
$\rho(G_{2}[X])\geq 3$ (by Observation 3.1), by Equations (1) and (2), it
follows that

$\rho(\hat{G}_{3})=\rho(\hat{G}_{2})+\rho(\hat{H})-\rho(G_{2}[X])\leq
1+3-3\leq 1.$

Since $\hat{H}\subsetneq\hat{G}_{3}\subseteq\hat{G}$ and
$\rho(\hat{G}_{3})<\rho(\hat{H})$, by claims (i), (ii), and (iii),
$\hat{G}_{3}$ is a larger subgraph of $\hat{G}$ than $\hat{H}$ which doesn’t
satisfy claim (iv). This contradicts our choice of $\hat{H}$ and completes the
proof. ∎

The following observation will aid in the proof of Lemma 3.5.

######  Observation 3.4.

Let $C$ be a cycle of a $C_{3}^{*}$-critical signed graph with a vertex of
degree $2$.

  1. (i)

If $C$ is a $4$-cycle, then $C$ is negative. If, additionally, $C$ has a chord
then the two triangles formed by this chord have different signs.

  2. (ii)

If $C$ is a $3$-cycle, then $C$ is positive.

To justify the observation, note that if $C$ does not have the prescribed
sign, then the subgraph formed by deleting the 2-vertex maps to $C_{3}^{*}$ if
and only if $\hat{H}$ does.

Let $\Theta_{1},\Theta_{2},\Theta_{3},$ and $X$ be the graphs depicted in
Figure 7(a) 7(b), 7(c), and 7(d), respectively.

${v_{1}}$${v_{2}}$${v_{3}}$${v_{4}}$ (a) $\Theta_{1}$

${v_{5}}$${v_{1}}$${v_{2}}$${v_{3}}$${v_{4}}$ (b) $\Theta_{2}$

${v_{1}}$${v_{2}}$${v_{3}}$${v_{4}}$${v_{5}}$ (c) $\Theta_{3}$

${v_{1}}$${v_{2}}$${v_{3}}$${v_{4}}$${v_{5}}$ (d) $X$

Figure 7: Graphs that are not a subgraph of $\hat{G}$.

######  Lemma 3.5.

$\hat{G}$ has no subgraph whose underlying graph is isomorphic to any of
$\Theta_{1},\Theta_{2},\Theta_{3}$, or $X$.

###### Proof.

We can easily compute that $\rho(\Theta_{1})=2$ and
$\rho(\Theta_{2})=\rho(\Theta_{3})=\rho(X)=3$. Let $\hat{H}$ be a subgraph of
$\hat{G}$ and $H\in\\{\Theta_{1},\Theta_{2},\Theta_{3},X\\}$.

Suppose that $H=\Theta_{1}$. By Lemma 3.3 (i), we conclude that
$G=\Theta_{1}$. By Lemma 2.9, it is not possible. Suppose that
$H\in\\{\Theta_{2},\Theta_{3},X\\}$. By Lemma 3.3 (i) and (ii), we conclude
that either $G=H$ or $G=P_{2}(H)$. If $H\in\\{\Theta_{2},\Theta_{3}\\}$, then
the former case is impossible by Lemma 2.9. If $H=X$, then the former case
would contradict that $\hat{G}$ is $C_{3}^{*}$-critical. Indeed, if $X$ could
be signed in a way that made it $C_{3}^{*}$-critical, then by Observation 3.4
(ii), it must have two triangles $v_{1}v_{2}v_{3}$ and $v_{3}v_{4}v_{5}$ both
being positive, which is switching equivalent to the signature that all the
edges of $\hat{X}$ are positive, and it is easy to see that when signed this
way $\hat{X}\to C_{3}^{*}$, a contradiction.

We are left to show that $P_{2}(\Theta_{2})$, $P_{2}(\Theta_{3})$, and
$P_{2}(X)$ each have no signature which makes them $C_{3}^{*}$-critical. We
consider them in order. In each case, let $v$ be the new vertex and let the
remaining vertices be labeled as in Figure 7. Suppose for contradiction that
$\sigma$ is a signature of each respective graph so that it is
$C_{3}^{*}$-critical.

  * •

For $P_{2}(\Theta_{2})$, $v$ must be adjacent to two of
$\\{v_{1},v_{3},v_{5}\\}$. Otherwise, the $4$-cycles $v_{1}v_{2}v_{5}v_{4}$,
$v_{1}v_{2}v_{3}v_{4}$ and $v_{5}v_{2}v_{3}v_{4}$, each containing a
$2$-vertex, would need to be negative by Observation 3.4 (i), but it is
impossible by the handshake lemma (i.e., the number of negative facial cycles
of a signed plane graph is even). Thus, without loss of generality, it must be
that $vv_{1},vv_{3}\in E(P_{2}(\Theta_{2}))$. Again by Observation 3.4 (i), we
need $P_{2}(\Theta_{2})$ to be assigned such that every $4$-cycle with a
$2$-vertex is negative and, by Lemma 2.1, it determines a unique (switching-
equivalent) signature $\sigma$. Note that up to switching we may assume that
$v_{1}v_{4}$ and $v_{2}v_{3}$ are the only negative edges in $\sigma$. But now
it is straightforward to verify that $(P_{2}(\Theta_{2}),\sigma)\to
C_{3}^{*}$, a contradiction.

  * •

For $P_{2}(\Theta_{3})$, $v$ must be adjacent to one of $v_{3}$ or $v_{4}$ by
Lemma 2.11 which forbids a $2_{1}$-vertex in any $C_{3}^{*}$-critical signed
graph. By symmetry, say $v$ is adjacent to $v_{3}$. If $v$ is also adjacent to
$v_{5}$, then the underlying graph is isomorphic to a $P_{2}(\Theta_{2})$, and
this case is complete. If $v$ is also adjacent to $v_{1}$, then the 4-cycles
$v_{1}v_{2}v_{3}v$ and $v_{5}v_{2}v_{3}v_{4}$ must be negative by Observation
3.4 (i). But then by assuming that three edges of $v_{1}v_{2}v_{3}$ are all
negative or all positive depending on the sign of the triangle, it is
straightforward to see the signed graph maps to $C_{3}^{*}$. The cases for $v$
being adjacent to $v_{2}$ or $v_{4}$ are omitted because they proceed as in
the previous case, where Observation 3.4 reduces the number of signatures to
be considered to one or two, and then, in a straightforward way, verifying
that a homomorphism to $C_{3}^{*}$ does exist.

  * •

For $P_{2}(X)$, it must be that $v$ is adjacent to a $2$-vertex in each of the
triangles $v_{1}v_{2}v_{3}$ and $v_{3}v_{4}v_{5}$ by Lemma 2.11 as there are
no two $2$-vertices adjacent to each other in any $C_{3}^{*}$-critical signed
graph.By symmetry, we may assume that $v$ is adjacent to $v_{2}$ and $v_{5}$.
But this graph is isomorphic to a $P_{2}(\Theta_{3})$ (i.e., $v$ is adjacent
to $v_{2}$ and $v_{3}$ in $P_{2}(\Theta_{3})$) and, by the previous case, it
cannot be the underlying graph of a $C_{3}^{*}$-critical signed graph.

This completes the proof. ∎

######  Corollary 3.6.

Every vertex of $\hat{G}$ is in at most one triangle.

###### Proof.

If a vertex is contained in two triangles, then, as a $C_{3}^{*}$-critical
graph has no parallel edges or digon, those two triangles must either (1)
share exactly one vertex, or (2) share exactly one edge. But both contradict
Lemma 3.5. ∎

######  Lemma 3.7.

Let $v$ be a $3_{1}$-vertex of $\hat{G}$ and $u$ be its $2$-neighbor. Assume
that $x$ and $y$ are the $3^{+}$-neighbors of $v$. Then the path $xvy$ must be
in a positive triangle.

$u$$v$$w$$y$$x$ Figure 8: A $3_{1}$-vertex with its neighbors.

###### Proof.

Let $w$ be the other neighbor of $u$ which is not $v$. See Figure 8. Suppose,
for a contradiction, that either the path $xvy$ is in a negative triangle or
$xy\not\in E(\hat{G})$. We consider these two possibilities:

  * •

Suppose that $xvy$ is a negative triangle. Let
$\hat{G}_{1}=\hat{G}-\\{u,v\\}$. It follows from the criticality of $\hat{G}$
that there is a homomorphism $\psi:\hat{G}_{1}\rightarrow C_{3}^{*}$. Let
$\sigma$ be a signature of $\hat{G}$ such that
$\psi:(\hat{G}_{1},\sigma|_{G_{1}})\rightarrow C_{3}^{*}$ is an edge-sign
preserving homomorphism with respect to $\sigma$. We will arrive at a
contradiction by showing that $\psi$ can be extended to $\hat{G}$. By possibly
switching on $u$ and $v$, we may assume $\sigma(uv)=\sigma(uw)=+$.

In the edge-sign preserving homomorphism $\psi:\hat{G}_{1}\rightarrow
C_{3}^{*}$, based on the sign of the edge $xy$, to determine $\psi(v)$ we have
two cases to consider: (1) If $\sigma(xy)=-$, then $\psi(x)=\psi(y)$. Because
$xvy$ is a negative triangle, it must be that $\sigma(xv)=\sigma(yv)$. If both
are negative, then set $\psi(v)=\psi(x)$, otherwise choose $\psi(v)\in
V(C^{*}_{3})\setminus\\{\psi(x)\\}$. (2) If $\sigma(xy)=+$, then
$\psi(x)\neq\psi(y)$ and $\sigma(xv)\neq\sigma(yv)$. Suppose without loss of
generality that $\sigma(xv)=-$ and then we set $\psi(v)=\psi(x)$. Now we
determine $\psi(u)$. Since $\sigma(uv)=\sigma(uw)=+$ we may extend $\psi$ by
setting $\psi(u)\in V(C^{*}_{3})\setminus\\{\psi(v),\psi(w)\\}$. Therefore,
$\hat{G}\rightarrow C_{3}^{*}$, a contradiction.

  * •

Suppose that $xy\not\in E(\hat{G})$. Let $\hat{G}_{1}=\hat{G}-\\{u,v\\}+xy$
and assign a sign to $xy$ such that $xvy$ is a negative triangle in
$\hat{G}+xy$. By the above reasoning, if $\hat{G}_{1}\rightarrow C_{3}^{*}$,
then also $\hat{G}\rightarrow C_{3}^{*}$, a contradiction. Thus
$\hat{G}_{1}\not\rightarrow C_{3}^{*}$, and so there exists
$\hat{G}_{2}\subseteq\hat{G}_{1}$ that is $C_{3}^{*}$-critical. Observe that
in constructing $\hat{G}_{2}$ we do not create any digon. Clearly, $xy\in
E(\hat{G}_{2})$ because otherwise $\hat{G}_{2}\subsetneq\hat{G}$ but both are
$C_{3}^{*}$-critical, a contradiction. Since $v(\hat{G}_{2})<v(\hat{G})-1$, by
the choice of $\hat{G}$, it follows that $\rho(\hat{G}_{2})\leq 1$. We then
define $\hat{G}_{3}=\hat{G}_{2}-xy$. Note that $\hat{G}_{3}\subsetneq\hat{G}$
and $\rho(\hat{G}_{3})=\rho(\hat{G}_{2})+2\leq 3$. Since $v(\hat{G}_{3})\leq
v(\hat{G})-2$, it follows that $\hat{G}\neq\hat{G}_{3}$ and $\hat{G}\neq
P_{2}(\hat{G}_{3})$. As $xy\not\in E(\hat{G}_{3})$,
$\hat{G}_{3}\not\in\\{K_{1},K_{3}\\}$. The existence of $\hat{G}_{3}$ is a
contradiction to Lemma 3.3.

This completes the proof. ∎

######  Lemma 3.8.

$\hat{G}$ contains no triangle $T$ of the following type.

  1. (i)

two $3_{1}$-vertices and a $4$-vertex;

  2. (ii)

a $3_{1}$-vertex and two $3$-vertices.

$x$$y$$v_{3}$$v_{1}$$x_{1}$$v_{2}$$x_{2}$(i)$T$$x$$y$$v_{2}$$v_{1}$$x_{1}$$v_{3}$(ii)$T$
Figure 9: The two cases in Lemma 3.8

###### Proof.

We proceed by cases. In each case, suppose for contradiction that the
described triangle $T$ does exist in $\hat{G}$. Let the vertices of $T$ be
labeled as is Figure 9. Note that as each $T$ contains a $3_{1}$-vertex, by
Lemma 3.7, $T$ is a positive triangle. Let $\mathcal{P}$ denote the set of
paths in $\hat{G}$ drawn in Figure 9 that join $v_{i}$ and one of
$x_{1},x_{2},x,y$ in $\hat{G}-E(T)$. By Lemma 3.5, there is no edge connecting
vertices $x$ and $y$ in $\hat{G}$.

(i). We add one edge $xy$ and assign it a signature such that $xv_{3}y$ is a
negative triangle. The resulting signed graph is denoted by
$\hat{G}^{\prime}$, i.e., $\hat{G}^{\prime}=\hat{G}+xy$. Let $\hat{H}$ denote
the signed graph obtained from $\hat{G}^{\prime}$ by deleting $V(T)$, and
$v_{1}$ and $v_{2}$’s $2$-neighbors.

First, we claim that $\hat{H}\not\rightarrow C_{3}^{*}$. Suppose for
contradiction there is a homomorphism $\psi:\hat{H}\rightarrow C_{3}^{*}$. Let
$\sigma$ be a signature of $\hat{G}^{\prime}$ such that $\psi$ is edge-sign
preserving. As in the proof of Lemma 2.14, we may assume the edges of $T$ are
positive, and that at most two of the paths in $\mathcal{P}$ are negative
under $\sigma$. Furthermore, by possibly switching on the set $V(T)$, we may
assume that the two paths of length $2$ in $\mathcal{P}$ are not both
negative. We consider two possibilities based on the sign of $xy$:

  * •

If the edge $xy$ is positive under $\sigma$, then because $v_{3}yx$ is a
negative triangle we may assume without loss of generality that $v_{3}x$ is
negative and $v_{3}y$ is positive. Moreover, if there is another negative path
in $\mathcal{P}$ (except $v_{3}x$), then by symmetry it is the
$v_{1}x_{1}$-path. Define $S_{1}=V(C_{3}^{*})\setminus\psi(x_{1})$,
$S_{2}=V(C_{3}^{*})$, and $S_{3}=\\{\psi(x)\\}$. By Lemma 2.13, we can choose
$\psi(v_{i})\in S_{i}$, for $i\in\\{1,2,3\\}$, such that $\psi:V(\hat{H})\cup
V(\hat{T})\to V(C_{3}^{*})$ is an edge-sign preserving homomorphism and then
by Observation 2.8 we may extend $\psi$ to a homomorphism of $\hat{G}$ to
$C^{*}_{3}$. Note that this is possible because $\psi(x)\neq\psi(y)$ since
$\sigma(xy)=+$, and so the ends of the edge $v_{3}y$ map to different vertices
of $C_{3}^{*}$. This contradicts that $\hat{G}$ is $C_{3}^{*}$-critical.

  * •

If $xy$ is negative under $\sigma$, then $\sigma(v_{3}x)=\sigma(v_{3}y)$ and
$\psi(x)=\psi(y)$. If $\sigma(v_{3}x)=-$, then $x_{1}v_{1}$-path and
$x_{2}v_{2}$-path are both positive, and in this case we define
$S_{1}=S_{2}=V(C_{3}^{*})$ and $S_{3}=\\{\psi(x)\\}$. If $\sigma(v_{3}x)=+$,
then by our assumptions there is at most one negative path in $\mathcal{P}$,
by symmetry say it is $x_{1}v_{1}$-path. In this case we define
$S_{1}=V(C_{3}^{*})\setminus\psi(x_{1})$, $S_{2}=V(C_{3}^{*})$, and
$S_{3}=V(C_{3}^{*})\setminus\psi(x)$. In either case, by Lemma 2.13, we may
choose $\psi(v_{i})\in S_{i}$ such that $\psi:V(\hat{H})\cup V(\hat{T})\to
V(C_{3}^{*})$ is an edge-sign preserving homomorphism and then, again, by
Observation 2.8 we may extend $\psi$ to $\hat{G}$, a contradiction.

Therefore, $\hat{H}\not\to C_{3}^{*}$.

Since $\hat{H}\not\to C_{3}^{*}$, we know that $\hat{H}$ contains a
$C_{3}^{*}$-critical subgraph $\hat{H}_{1}$. Moreover, $\hat{H}_{1}$ must
contain the edge $xy$ because otherwise $\hat{H}_{1}\subsetneq G$,
contradicting that they are both $C_{3}^{*}$-critical. Noting that
$v(\hat{H}_{1})<v(\hat{G})-1$, by the minimality of $\hat{G}$,
$\rho(\hat{H}_{1})\leq 1$. Let $\hat{H}_{2}=\hat{H_{1}}-xy$ and note that
$\rho(\hat{H}_{2})=\rho(\hat{H}_{1})+2\leq 3$. As $\hat{H}_{2}$ is a subgraph
of $\hat{G}$, by Lemma 3.3, either $\hat{H}_{2}=\hat{G}$, or
$\hat{G}=P_{2}(\hat{H}_{2})$, or $\hat{H}_{2}\in\\{K_{1},K_{3}\\}$, but all of
these are impossible. The first two cannot be because five vertices were
deleted in $\hat{G}$ to form $\hat{H}$, and the last because of the deleted
edge $xy$.

(ii). As in Case (i), add one edge $xy$ but assign it a signature so that
$v_{2}v_{3}yx$ is a positive 4-cycle. Denote the resulting signed graph by
$\hat{G}^{\prime}$. Let $\hat{H}$ be the signed graph obtained from
$\hat{G}^{\prime}$ by deleting the vertices of $T$ and the 2-vertex adjacent
to $v_{1}$.

First, we claim that $\hat{H}\not\rightarrow C_{3}^{*}$. Suppose for
contradiction there is a homomorphism $\psi:\hat{H}\rightarrow C_{3}^{*}$. Let
$\sigma$ be a signature of $\hat{G}^{\prime}$ which admits $\psi$ as edge-sign
preserving. Once again, we may assume that all the edges of $T$ are positive
and that at most one of the paths in $\mathcal{P}$ is negative under $\sigma$.
We consider two cases based on the sign of $xy$.

  * •

If $xy$ is negative under $\sigma$, then since $v_{2}v_{3}yx$ is a positive
4-cycle we may assume without loss of generality that $v_{2}x$ is the only
negative path in $\mathcal{P}$. Define $S_{1}=V(C_{3}^{*})$,
$S_{2}=\\{\psi(x_{2})\\}$, and $S_{3}=V(C_{3}^{*})\setminus\\{\phi(y)\\}$. By
Lemma 2.13, we may choose $\psi(v_{i})\in S_{i}$ such that
$\psi:V(\hat{H})\cup V(\hat{T})\to V(C_{3}^{*})$ is an edge-sign preserving
homomorphism and then, again, by Observation 2.8 we may extend $\psi$ to
$\hat{G}$, a contradiction.

  * •

If $xy$ is positive under $\sigma$, then $v_{2}x$ and $v_{3}y$ are also
positive, and $\psi(x)\neq\psi(y)$. Define
$S_{i}=V(C_{3}^{*})\setminus\phi(v_{i})$ for $i=1,2,3$. Then $|S_{i}|=2$ for
each $i$, but $S_{2}\cup S_{3}=V(C_{3}^{*})$. Hence by Lemma 2.13 we can
choose $\psi(v_{i})\in S_{i}$ such that $\psi:V(\hat{H})\cup V(\hat{T})\to
V(C_{3}^{*})$ is an edge-sign preserving homomorphism and then extend $\psi$
to $\hat{G}$ by Observation 2.8, a contradiction.

Therefore, $\hat{H}\not\to C_{3}^{*}$.

Since $\hat{H}\not\rightarrow C_{3}^{*}$, this means $\hat{H}$ has a
$C_{3}^{*}$-critical subgraph $\hat{H_{1}}$, which contains the edge $xy$.
This leads to a contradiction in the same manner as Case (i), and we do not
repeat the details.

This completes the proof of the lemma. ∎

######  Lemma 3.9.

Let $v$ be a $4$-vertex of $\hat{G}$ with two $2$-neighbors $u$ and $w$.
Suppose that $x$ and $y$ are the other neighbors of $v$. Then either $xvy$ is
a positive triangle, or $xvy$ is a path in a negative $4$-cycle.

$x$$y$$v$$u$$u^{\prime}$$w$$w^{\prime}$ Figure 10: A $4$-vertex with two
$2$-neighbors.

###### Proof.

Let $u^{\prime}$ and $w^{\prime}$ be the neighbors of $u$ and $w$ respectively
that are not $v$. See Figure 10. Let $\sigma$ = $\sigma(\hat{G})$. Suppose for
contradiction that $xvy$ is neither in a positive triangle nor a negative
$4$-cycle. By possibly switching, we may assume that $\sigma(vx)=\sigma(vy)$
and $\sigma(xy)=-$ if there exists one such edge. If $v^{\prime}\neq v$ is a
common neighbor of $x$ and $y$, then it must be that also
$\sigma(v^{\prime}x)=\sigma(v^{\prime}y)$ because otherwise, $xvyv^{\prime}$
is a negative 4-cycle. Let $\hat{G}_{1}$ be the signed graph obtained from
$\hat{G}$ by identifying $x$ and $y$ to a new vertex $z$ and deleting one of
the parallel edges connecting $z$ and $v$.

Since any common neighbor $v^{\prime}$ of $x$ and $y$ has
$\sigma(v^{\prime}x)=\sigma(v^{\prime}y)$, the graph $\hat{G}_{1}$ has no
digon. Since $\sigma(xy)=-$, if such an edge exists, then $\hat{G}_{1}$ may
have a negative loop but no positive loop. If there is a homomorphism
$\psi:\hat{G}_{1}\rightarrow C_{3}^{*}$, then $\psi$ can be extended to
$\hat{G}$ by setting $\psi(x)=\psi(y)=\psi(z)$. This contradicts that
$\hat{G}$ is $C_{3}^{*}$-critical. Thus $\hat{G}_{1}\not\rightarrow
C_{3}^{*}$, and hence $\hat{G}_{1}$ contains a $C_{3}^{*}$-critical subgraph
$\hat{G}_{2}$. Note that $z\in V(\hat{G}_{2})$ because otherwise
$\hat{G}_{2}\subsetneq\hat{G}$, but both are $C_{3}^{*}$-critical, a
contradiction.

Now we claim that the vertex $v$ is not in $\hat{G}_{2}$. Otherwise, $v$ is a
vertex of one of the following types: $1$-vertex, $2_{1}$-vertex, or
$3_{2}$-vertex, contradicting Lemma 2.11 or 2.12. Note that $u$ and $w$ are
also not in $\hat{G}_{2}$ since $\hat{G}_{2}$ must be connected and contains
no cut-edge by Lemma 2.10. Clearly, $v(\hat{G}_{2})<v(\hat{G})-1$, so
$\rho(\hat{G}_{2})\leq 1$ by the minimality of $\hat{G}$.

We now construct a signed graph $\hat{G}_{3}$ from $\hat{G}_{2}$ as follows:
firstly, undo the identification at $z$, without putting back the negative
edge $xy$ if such an edge exists; secondly, add the vertex $v$ and edges $vx$
and $vy$. Note that $\hat{G}_{3}$ is a proper subgraph of $\hat{G}$ and
$\rho(\hat{G}_{3})=\rho(\hat{G}_{2})+6-4\leq 3$. Since
$\hat{G}_{3}\subsetneq\hat{G}$, by Lemma 3.3, one of the following conditions
is satisfied: (1) $\hat{G}=\hat{G}_{3}$, (2) $\hat{G}=P_{2}(\hat{G}_{3})$, (3)
${G}_{3}=K_{1}$, or (4) ${G}_{3}=K_{3}$. But (1) and (2) are not possible
because $u,w\in V(\hat{G})\setminus V(\hat{G}_{3})$, and (3) and (4) are not
satisfied because $x,y\in V(\hat{G}_{3})$ but are not adjacent. This
contradiction completes the proof. ∎

The next lemma shows us that every $4_{3}$-vertex of $\hat{G}$ is in exactly
three $4$-cycles, all of which share exactly one common edge.

######  Lemma 3.10.

Let $v$ be a $4_{3}$-vertex of $\hat{G}$, and let $w$ be its neighbor which is
not of degree $2$. Then the distance-two neighbors of $v$ are distinct, and
$w$ is adjacent to each of them.

$x_{1}$$x_{2}$$x_{3}$$v_{1}$$v_{2}$$v_{3}$$v$$w$$\to$$x_{1}$$x_{2}$$x_{3}$$v_{1}$$v_{2}$$v_{3}$$v$$w$
Figure 11: A $4_{3}$-vertex and its neighborhood.

###### Proof.

Let $v\in V(\hat{G})$ be a $4_{3}$-vertex whose neighborhood is labeled as in
Figure 11. Since $\hat{G}$ contains no copy of $\Theta_{2}$, by Lemma 3.5,
$x_{1},x_{2},$ and $x_{3}$ are not identified. By Lemma 3.9, for each $i$,
either $w=x_{i}$ or $wx_{i}$ is an edge. First, we show that $w\neq x_{i}$ for
any $i$. If there are distinct $i$ and $j$ such that $w=x_{i}=x_{j}$, then
$\\{w,v,v_{i},v_{j}\\}$ induces a copy of $\Theta_{1}$, contradicting Lemma
3.5. If there are $i$ and $j$ such that $w=x_{i}$ and $wx_{j}$ is an edge,
then $\\{w,v,v_{i},v_{j},x_{j}\\}$ induces a copy of $\Theta_{3}$, again
contradicting Lemma 3.5. Therefore, $w\neq x_{i}$ for any $i$, which means
$wx_{1},wx_{2}$ and $wx_{3}\in E(\hat{G})$. Finally, if there exist distinct
$i,j$ such that $x_{i}=x_{j}$, then $\\{w,v,v_{i},v_{j},x_{i}\\}$ induces a
copy of $\Theta_{2}$, a contradiction. ∎

######  Lemma 3.11.

  1. (1)

No $5_{\geq 2}$-vertex is adjacent to a $4_{3}$-vertex in $\hat{G}$.

  2. (2)

No $4_{0}$-vertex is adjacent to two $4_{3}$-vertices in $\hat{G}$.

  3. (3)

No $5$-vertex is adjacent to four $4_{3}$-vertices in $\hat{G}$.

$w$$v$$x_{1}$$x_{2}$$x_{3}$ Figure 12: The subgraph $H$ which arises when a
$4_{0}$-vertex $w$ is adjacent to two $4_{3}$-vertices $v$ and $x_{3}$.

$w$$x_{1}$$x_{2}$$x_{3}$$x_{4}$$w^{\prime}$ Figure 13: The subgraph which
arises when a $5$-vertex $w$ is adjacent to four $4_{3}$-vertices $x_{1}$ to
$x_{2}$.

###### Proof.

(1) Let $v$ be the $4_{3}$-vertex and its neighborhood be labeled as in Figure
11. Suppose for contradiction $w$ is a $5_{\geq 2}$-vertex. Then some $x_{i}$
must be a $2$-vertex, but this contradicts Lemma 2.11, which forbids a
$2_{1}$-vertex in $\hat{G}$.

(2) Suppose for contradiction such a $4_{0}$-vertex exists. Let $v$ be one of
its $4_{3}$-neighbors, and let the neighborhood of $v$ be labeled as in Figure
11. The $4_{0}$-vertex is clearly $w$, and by Lemma 3.10, the other
$4_{3}$-vertex must be some $x_{i}$, say $x_{3}$. Applying Lemma 3.10 to the
$4_{3}$-vertex $x_{3}$, it follows that $x_{1}$ and $x_{2}$ are at distance
$2$ from $x_{3}$, as in Figure 13. But then the signed graph $\hat{H}$ induced
by $v,w,x_{1},x_{2},x_{3}$ and the five $2$-neighbors of $v$ and $x_{3}$ has
$10$ vertices and $14$ edges. This means $\rho(H)=2$. By Lemma 3.3, it must be
that $\hat{H}=\hat{G}$. But this is impossible because $\hat{H}$ has a
$3_{2}$-vertex $x_{1}$, contradicting Lemma 2.12.

(3) Suppose for contradiction that such a $5$-vertex $w$ exists. Let
$x_{1},x_{2},x_{3},$ and $x_{4}$ be its $4_{3}$-neighbors, and let
$w^{\prime}$ be the remaining neighbor of $w$. By Lemma 3.10, for each $i$,
the $3$ distance-two neighbors of $x_{i}$ are among $\\{w^{\prime},x_{j}:j\neq
i\\}$. Now, by parity, $w^{\prime}$ is adjacent to $0,2$, or $4$ of the
$x_{i}$’s. If $w^{\prime}$ is adjacent to $2$ (or $4$) of them, then the
subgraph $\hat{H}$ induced by $\\{w,w^{\prime},x_{1},x_{2},x_{3},x_{4}\\}$ and
the $2$-neighbors of each $x_{i}$ has $\rho(\hat{H})=1$ (or $0$,
respectively). Both contradict Lemma 3.3. This means each $x_{i}$ is pairwise
connected by a path of length two, where the internal vertex of each path has
degree $2$, and $w^{\prime}$ is adjacent to none of $w_{i}$’s, as depicted in
Figure 13. But then the edge $w^{\prime}w$ is a cut-edge in $\hat{G}$,
contradicting Lemma 2.10. ∎

### Discharging part

We define a _wealthy vertex_ to be a vertex of one of the following types: a
$4_{0}$-vertex, a $5_{\leq 2}$-vertex, or a $6^{+}$-vertex, and a _rich
vertex_ to be a vertex of one of the following types: a $4_{1}$-vertex, a
$5_{3}$-vertex, or a wealthy vertex.

In the next lemma, we show that every $3_{1}$-vertex has a “good” neighbor.

######  Lemma 3.12.

Every pair of adjacent $3_{1}$-vertices has a common wealthy neighbor and
every $3_{1}$-vertex has a rich neighbor.

###### Proof.

Let $v$ be a $3_{1}$-vertex, and $w,u$ be its neighbors of degree at least
$3$. By Lemma 3.7, $w$ and $u$ are adjacent.

First, suppose that $v$ has a $3_{1}$-neighbor, say $u$. In this case, we
shall show that $w$ is wealthy. By Lemma 3.8, $w$ has degree at least $5$. If
$w$ has degree exactly $5$, then $w$ is a $5_{\leq 3}$-vertex because of its
neighbors $v$ and $u$. But by Lemma 2.14 (i), $w$ is not a $5_{3}$-vertex.
This means $w$ is either a $5_{\leq 2}$-vertex or a $6^{+}$-vertex, so $w$ is
wealthy by definition.

Now suppose that $v$ does not have a $3_{1}$-neighbor. In this case, we shall
show that one of $w$ or $u$ is rich. If either is of degree at least $5$, then
it is rich. So we may assume each of $w$ and $u$ is of degree at most $4$.
Suppose that one of them is of degree $3$, say $w$. By Lemma 3.8 (ii), $u$ has
degree $4$. By Lemma 2.14 (iii), $u$ is a $4_{\leq 1}$-vertex, so $u$ is rich.
So we may assume each of $w$ and $u$ is of degree exactly $4$. Then by Lemma
2.14 (ii), one of them is a $4_{\leq 1}$-vertex, which is rich. ∎

Then we show that every $4_{3}$-vertex also has a “good” neighbor.

######  Lemma 3.13.

Every $4_{3}$-vertex is adjacent to a (unique) wealthy vertex $w$ in
$\hat{G}$. Moreover, if $w$ is in a triangle, then it is of degree at least
$6$.

###### Proof.

Let $v$ be a $4_{3}$-vertex, $w$ its non-$2$-neighbor, and whose neighborhood
is otherwise labeled as in Figure 11. Since $2_{1}$-vertices are forbidden by
Lemma 2.11, for $i\in\\{1,2,3\\}$ each $x_{i}$ has degree at least $3$. By
Lemma 3.10, $w$ is adjacent to each distinct $x_{i}$. This means $w$ is of
degree at least $4$ and moreover, none of its four labeled neighbors is of
degree $2$. By the definition, $w$ is a wealthy vertex.

For the moreover part, observe that if $w$ is in a triangle and is of degree
at most $5$, then there must be a copy of $\Theta_{3}$, contradicting Lemma
3.5. ∎

Now we are ready to apply the discharging method. We begin with every vertex
having a charge equal to its degree. Thus

$\sum\limits_{v\in V(\hat{G})}c(v)=\sum\limits_{v\in
V(\hat{G})}d(v)=2e(\hat{G})\leq 3v(\hat{G})-2.$

We then apply the following three discharging rules to each vertex $v$ in
$\hat{G}$.

  1. (Rule 1)

Every $3^{+}$-vertex gives a charge of $\frac{1}{2}$ to each of its
$2$-neighbors.

  2. (Rule 2)

Every rich vertex gives a charge of $\frac{1}{2}$ to each of its
$3_{1}$-neighbors.

  3. (Rule 3)

Every wealthy vertex gives a charge of $\frac{1}{2}$ to each of its
$4_{3}$-neighbors.

We claim that after discharging, each vertex has a charge of at least $3$,
thus

$\sum\limits_{v\in V(\hat{G})}c(v)=\sum\limits_{v\in
V(\hat{G})}c^{\prime}(v)\geq 3v(\hat{G}),$

a contradiction.

Let $v\in V(\hat{G})$. We consider three cases based on the type of $v$.

Case (1). Assume that $v$ is not rich. This means $v$ is one of the following
types: a $2$-vertex, a $3$-vertex, a $4_{\geq 2}$-vertex, or a $5_{\geq
4}$-vertex. The vertex $v$ may give charge only to its $2$-neighbors (if
exists) via Rule 1, and may receive charge via Rule 2 or 3.

If $v$ has degree $2$, then by Lemma 2.11, there is no $2_{1}$-vertex and $v$
has two neighbors of degree at least $3$. By Rule 1, $v$ receives a charge of
$\frac{1}{2}$ from each of them. And since $v$ gives no charge to any
neighbor, after discharging $v$ has a charge of $3$.

If $v$ is one of $3_{0}$-vertex, $4_{2}$-vertex, or $5_{4}$-vertex, then it
has sufficient charge to give to each of its $2$-neighbors (if exists) such
that it ends with a charge of $3$.

By Lemma 2.12, there exists no $3_{2}$-vertex and by lemma 2.11, there exists
no $4_{4}$-vertex and no $5_{5}$-vertex. Hence, the only remaining cases are
when $v$ is a $3_{1}$-vertex or $4_{3}$-vertex. By Lemmas 3.12 and 3.13, via
Rule 2 or 3, each of these vertices receives a charge of at least
$\frac{1}{2}$ from some rich or wealthy neighbor. Therefore, after giving a
charge $\frac{1}{2}$ to each of its $2$-neighbors and receiving a charge
$\frac{1}{2}$ from its rich or wealthy neighbor, it ends up with a charge of
$3$.

Case (2). Assume that $v$ is rich but not wealthy. This means $v$ is either a
$4_{1}$-vertex or $5_{3}$-vertex, and thus it may only give charge to its
neighbors via Rules 1 and 2. By Lemma 3.7, if $v$ is adjacent to a
$3_{1}$-vertex $x$, then it is in a triangle with $x$. By Corollary 3.6, $v$
is in at most one triangle. If $v$ is adjacent to two $3_{1}$-vertices, say
$x,x^{\prime}$, then $v,x,x^{\prime}$ are in a triangle. But by the moreover
part of Lemma 3.12, this means $v$ is wealthy, a contradiction. Hence, $v$ is
adjacent to at most one $3_{1}$-vertex. This means $v$ gives a charge of at
most $\frac{1}{2}$ via Rule 2. Thus after giving a charge $\frac{1}{2}$ to its
$2$-neighbors via Rule 1, it still has a charge of at least $3$.

Case (3). Assume that $v$ is wealthy. This means $v$ is one of the following
types: a $6^{+}$-vertex, a $4_{0}$-vertex, or a $5_{\leq 2}$-vertex. If $v$ is
a $6^{+}$-vertex, then by Rules 1, 2, and 3, after discharging it always has a
charge of $d(v)-\frac{1}{2}d(v)\geq 3$.

Hence, we may assume $v$ is either a $4_{0}$-vertex, or a $5_{\leq 2}$-vertex.
Note that by Lemma 3.13, Rules 2 and 3 cannot apply at the same time to $v$.
By Corollary 3.6, $v$ is in at most one triangle and can therefore give a
charge of at most $1$ via Rule 2. Thus after applying Rules 1 and 2, $v$ is
left with a charge of at least $3$. It remains only to consider when Rule 3 is
applied. By Lemma 3.11 (1), if $v$ is a $5_{2}$-vertex, it has no
$4_{3}$-neighbor, and so gives no charge under Rule 3. By Lemma 3.11 (2), $v$
is adjacent to at most one $4_{3}$-vertex if it is a $4_{0}$-vertex, and by
Lemma 3.11 (3), $v$ is adjacent to at most three $4_{3}$-vertices if it is a
$5_{\leq 1}$-vertex. This means after applying Rules 1 and 3, $v$ still has a
charge of at least $3$.

We are done.

##  4 Tightness and discussion

We have seen in Lemma 2.7 that $\hat{W}$ is a $C^{*}_{3}$-critical signed
graph satisfying that $e(\hat{W})=\frac{3v(\hat{W})-1}{2}$. Now we provide a
sequence of $C^{*}_{3}$-critical signed graphs with edge density
$\frac{3}{2}$, showing that the bound in Theorem 1.5 is asymptotically tight.

Let $\hat{S}_{k}$ be the connected signed graph obtained from a negative cycle
of length $k$ by adding a set $S$ of $k$ vertices and $2k$ edges so that each
edge of the negative cycle is contained in a positive triangle with a distinct
vertex in $S$, as in Figure 15. It is easy to observe that
$e(\hat{S}_{k})=\frac{3v(\hat{S}_{k})}{2}.$ Note that in any edge-sign
preserving homomorphism of a switching-equivalent $\hat{S}_{k}$ to
$C_{3}^{*}$, every edge of each triangle needs to be positive. Hence, such a
signature does not exist because $\hat{S}_{k}$ has a negative $k$-cycle which
requires at least one negative edge appearing in one triangle. Therefore
$\hat{S}_{k}\not\to C_{3}^{*}$. Furthermore, there is a signature of
$\hat{S}_{k}$ with exactly two negative edges (both in the same triangle). If
any edge $e$ is deleted, then by symmetry we may assume it is one of those two
negative edges, and with this signature $\hat{S}_{k}-e\to C_{3}^{*}$. So
$\hat{S}_{k}$ is $C_{3}^{*}$-critical.

$+$$+$$+$$+$$+$$+$$+$$+$$+$$-$ Figure 14: Signed graph $\hat{S}_{k}$

${v_{1}}$${v_{2}}$${v_{3}}$${v_{4}}$${v_{5}}$${u_{1}}$${u_{2}}$${u_{3}}$${u_{4}}$${u_{5}}$

${v_{1}}$${v_{2}}$${v_{3}}$${v_{4}}$${v_{5}}$${u_{1}}$${u_{2}}$${u_{3}}$${u_{4}}$${u_{5}}$

Figure 15: Signed Petersen graph $\hat{P}$

Next, we shall prove that the girth bound in Corollary 1.3 for the class of
signed projective-planar graphs is tight. We show that there is a signed
projective-planar graph of girth $5$ which does not admit a homomorphism to
$C^{*}_{3}$ in the next lemma.

Let $\hat{P}$ be a signed Petersen graph with a signature such that the edges
of one $5$-cycle are negative and all the other edges are positive, depicted
in Figure 15. We note that $\hat{P}$ is a signed projective-planar graph of
girth $5$.

######  Lemma 4.1.

The signed graph $\hat{P}$ is $C^{*}_{3}$-critical.

###### Proof.

It is easy to see that for any edge $e$, $\hat{P}-e$ satisfies that
$\rho(\hat{P}-e)=2$. Hence, by Theorem 3.2 and because of the degrees of the
vertices of $\hat{P}-e$, it does not contain any $C^{*}_{3}$-critical signed
graph as a subgraph and thus it admits a homomorphism to $C^{*}_{3}$.

Proving that $\hat{P}$ does not admit a homomorphism to $C^{*}_{3}$ is a bit
more technical. For a contradiction, assume that there exists such a mapping.
First, observe that any mapping of a positive $5$-cycle to $C^{*}_{3}$ covers
all positive edges of the target while it is the opposite for negative
$5$-cycles (at least one positive edge of $C^{*}_{3}$ is not used as the
homomorphic image of an edge of a negative $5$-cycle). By the high symmetry of
the signed Petersen graph, observe also that any negative $5$-cycle can be
isomorphically seen as the central cycle, denoted by
$S=u_{1}u_{3}u_{5}u_{2}u_{4}$, depicted in Figure 15. Let us study how a
negative $5$-cycle can be mapped to $C^{*}_{3}$ and let $a,b$ and $c$ denote
the vertices of $C^{*}_{3}$.

  1. (1)

All vertices $u_{1}$ up to $u_{5}$ of the negative cycle $S$ are mapped to one
vertex of $C^{*}_{3}$, say $a$. Since $v_{1}u_{1}u_{4}u_{2}v_{2}$ is a
positive $5$-cycle, it should cover all the positive edges of the target
$C^{*}_{3}$ so $v_{1}$ and $v_{2}$ should be mapped to $b$ and $c$
respectively. The same argument stands for the pairs $v_{2}v_{3}$,
$v_{3}v_{4}$, $v_{4}v_{5}$, and $v_{5}v_{1}$. This is impossible since the
$5$-cycle is not bipartite. So no negative $5$-cycle has all its vertices
mapped to a single vertex of $C^{*}_{3}$.

  2. (2)

Four vertices of $S$, say $u_{1}$ up to $u_{4}$, are mapped to one vertex of
$C^{*}_{3}$, say $a$ and the vertex $u_{5}$ is mapped to $b$. Then,
considering the positive cycles $u_{1}u_{3}v_{3}v_{4}u_{4}$ and
$u_{1}v_{1}v_{2}u_{2}u_{4}$ whose homomorphic images should cover all the
positive edges of the target signed graph $C^{*}_{3}$, we may conclude that
$\\{v_{1},v_{2}\\}$ is mapped to $\\{b,c\\}$ and so does $\\{v_{3},v_{4}\\}$.
Now if $v_{1}$ is mapped to $b$ and $v_{2}$ to $c$, then the homomorphism
image of the negative $5$-cycle $v_{1}v_{2}u_{2}u_{5}v_{5}$ already covers all
positive edges of $C^{*}_{3}$ which is a contradiction with our first
observation. The same result holds for the pair $\\{v_{3},v_{4}\\}$. Thus it
implies that both $v_{1}$ and $v_{4}$ are mapped to $c$ while both $v_{2}$ and
$v_{3}$ are mapped to $b$. This prevents the positive (outer) $5$-cycle
$v_{1}v_{2}v_{3}v_{4}v_{5}$ to be mapped to $C^{*}_{3}$, as wherever $v_{5}$
is mapped it will not cover the edge $ab$. So no negative $5$-cycle has four
of its vertices mapped to a single vertex of $C^{*}_{3}$.

  3. (3)

Three consecutive of $S$, say $u_{3},u_{1}$ and $u_{4}$, are mapped to $a$. In
this case, both other vertices $u_{2}$ and $u_{5}$ must be mapped to the same
vertex, say $b$, to preserve the sign of the cycle. Since
$v_{3}u_{3}u_{1}u_{4}v_{4}$ is a positive $5$-cycle, we may assume without
loss of generality that $v_{3}$ is mapped to $b$ while $v_{4}$ is mapped to
$c$. But then the edges of the negative $5$-cycle $u_{2}v_{2}v_{3}v_{4}u_{4}$
already cover all positive edges of the target $C^{*}_{3}$ which is a
contradiction. So no three consecutive vertices of a negative $5$-cycle can be
mapped to a single vertex of $C^{*}_{3}$.

Most of the technical part is done. Now observe that any three consecutive
vertices (i.e., vertices that induce a path) of $\hat{P}$ are involved in a
negative $5$-cycle. Together with our previous case study, this implies that
no three vertices of a $3$-path can be mapped to a single vertex of
$C^{*}_{3}$. In other words, any switching-equivalent signature $\pi$ of
$\hat{P}$ that allows an edge-sign preserving homomorphism of $(P,\pi)$ to
$C^{*}_{3}$ does not have two incident negative edges. Up to isomorphism, only
one switching-equivalent signature $\pi$ of $\hat{P}$ achieves this and it is
on the right of Figure 15. If such an edge-sign preserving homomorphism was
possible, then $v_{2}$ and $v_{3}$ are mapped to $a$, $v_{4}$ and $v_{5}$ are
mapped to $b$, and $u_{2}$ and $u_{5}$ are mapped to $c$. In order to prevent
the vertices of any $3$-path being mapped to a single vertex, it enforces
$u_{3}$ to be mapped to $b$, $u_{4}$ to $a$, and $v_{1}$ to $c$. But then
$u_{1}$ cannot be mapped anywhere while preserving the sign of its incident
edges. This concludes the proof that $\hat{P}$ does not admit a homomorphism
to $C^{*}_{3}$. ∎

Actually, in a personal communication of the fifth author with R. Naserasr and
S. Mishra, it has been shown that $\chi_{c}(\hat{P})=\frac{10}{3}$ which also
implies that $\hat{P}\not\to C^{*}_{3}$. Here we give the shortest proof that
we could achieve for the sake of completeness.

However, we don’t know if the girth bound of $6$ in Corollary 1.3 is tight for
the class of signed planar graphs.

We have seen in Theorem 1.1 that if a graph $G$ satisfies that
$e(G)<\frac{5v(G)-2}{3}$, then $G\to C_{3}$. Hence, any graph $G$ with average
degree less than $\frac{10}{3}-\frac{4}{3v(G)}$ is $3$-colorable. It implies
Brook’s theorem when $\Delta=3$, i.e., except $K_{4}$ (where $v(K_{4})=4$),
any graph on more than $4$ vertices with maximum degree $3$ is $3$-colorable.
The previous argument means that the $C_{3}$-critical graph with $\Delta=3$ is
unique and it is $K_{4}$. We may consider the analogous problem for
$C^{*}_{3}$-critical signed graphs. It has been proved in Theorem 1.5 that if
a signed graph $\hat{G}$ satisfies that $e(\hat{G})<\frac{3v(\hat{G})-1}{2}$,
then $\hat{G}\to C^{*}_{3}$. Thus any signed graph with its average degree
less than $3-\frac{1}{v(G)}$ is circular $3$-colorable. We pose the following
question:

######  Problem 4.2.

Are there finitely many $C^{*}_{3}$-critical signed graphs with $\Delta=3$?

#### Acknowledgement.

This work was initiated as a group project at the ANR-HOSIGRA Workshop, held
at CAES du CNRS La Villa Clythia in Fréjus, France in May 2022. The authors
wish to thank ANR project HOSIGRA (ANR-17-CE40-0022) for providing this
support.

The second and third authors were partially supported by the Natural Sciences
and Engineering Research Council of Canada (NSERC). The fourth author was
partially funded by IFCAM project “Applications of graph homomorphisms”
(MA/IFCAM/18/39) for this work. The fifth author was partially supported by
European Union’s Horizon 2020 research and innovation program under the Marie
Sklodowska-Curie grant agreement No 754362.

## References

  * [1] Brooks, R. L. On Coloring the Nodes of a Network.  Proc. Cambridge Philos. Soc. 37, (1941) 194–197.
  * [2] Cranston, D.W. and Li, J. Circular flows in planar graphs.  SIAM J. Discrete Math., 34 (2020) 497–519.
  * [3] Dvořák, Z. and Postle, L. Density of 5/2-critical graphs.  Combinatorica 37, 5(2017) 863–886.
  * [4] Grötzsch, H. Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel.  Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe, 8 (1959), pp. 109-120
  * [5] Han, M., Li, J., Wu, Y., and Zhang, C.-Q. Counterexamples to Jaeger’s circular flow conjecture.  J. Combin. Theory Ser. B 131, (2018), 1-11.
  * [6] Jaeger, F. On circular flows in graphs.  In Finite and infinite sets, North-Holland., (1984) (pp. 391-402).
  * [7] Jaeger, F. Nowhere-zero flow problems.  Selected Topics in Graph Theory 3, (L. W. Beineke and R. J. Wilson eds.), Academic Press, London, (1988) 71-95.
  * [8] Kardoš, F. and Narboni, J. On the 4-color theorem for signed graphs.  European J. Combin., 91 (2021) 103215.
  * [9] Kardoš, F., Narboni, J., Naserasr, R., and Wang, Z. Circular $(4-\epsilon)$-coloring of some classes of signed graphs.  Accepted by SIAM J. Discrete Math. (2023)
  * [10] Kostochka, A. and Yancey, M. Ore’s conjecture on color-critical graphs is almost true.  J. Combin. Theory Ser. B 109, 3(2014) 73–101.
  * [11] Kostochka, A. and Yancey, M. Ore’s conjecture for $k=4$ and Grötzsch’s theorem.  Combinatorica 34, 3(2014) 323–329.
  * [12] Lovász, L. Three short proofs in graph theory.  J. Combin. Theory Ser. B 19, 3(1975) 269–271.
  * [13] Lovász, L. M., Thomassen, C., Wu, Y., and Zhang, C.-Q. Nowhere-zero 3-flows and modulo k-orientations.  J. Combin. Theory Ser. B 103, 5(2013) 587–598.
  * [14] Máčajová, E., Raspaud, A., and Škoviera, M. The chromatic number of a signed graph.  Electron. J. Combin. 23, 1(2016) paper 1.14.
  * [15] Naserasr, R., Pham, L.A., and Wang, Z. Density of $C_{-4}$-critical signed graphs.  J. Combin. Theory Ser. B, 153(2022), 81–104.
  * [16] Naserasr, R., Rollová, E., and Sopena, E. Homomorphisms of signed graphs.  J. Graph Theory 79, 3(2015), 178–212.
  * [17] Naserasr, R., Sopena, É., and Zaslavsky, T. Homomorphisms of signed graphs: An update.  European J. Combin., 91(2021), 103222.
  * [18] Naserasr, R., Škrekovski, R., Wang, Z., and Xu, R. Mapping sparse signed graphs to $(K_{2k},M)$.  Accepted by J. Graph Theory (2023)
  * [19] Naserasr, R. and Wang, Z. Signed bipartite circular cliques and a bipartite analogue of Grötzsch’s theorem.  arXiv:2109.12618 (2022)
  * [20] Naserasr, R., Wang, Z., and Zhu, X. Circular chromatic number of signed graphs.  Electron. J. Combin. 28, 2(2021), P2.44
  * [21] Ore, O. The Four Color Problem.  Academic Press, New York (1967)
  * [22] Postle, L. and Smith-Roberge, E. On the Density of $C\\_7$-Critical Graphs.  Combinatorica (2022), 48pp. DOI:10.1007/s00493-020-4177-y
  * [23] West, D. Introduction to graph theory.  Prentice Hall, Inc., Upper Saddle River, NJ, (1996) xvi+512.
  * [24] Zaslavsky, T. Signed graphs.  Discrete Appl. Math. 4, 1(1982) 47–74.
  * [25] Zaslavsky, T. Signed graph coloring.  Discrete Math., 39(1982) 215–228.