Clément Charpentier

Reza Naserasr

Éric Sopena

Homomorphisms of sparse signed graphs

Keywords: Signed graph, homomorphism, sparse graph, planarity. MSC 2010: 05C22, 05C15, 05C38

The notion of homomorphism of signed graphs, introduced quite recently, provides better interplay with the notion of minor and is thus of high importance in graph coloring. A newer, but equivalent, definition of homomorphisms of signed graphs, proposed jointly by the authors of this paper and Tom Zaslavsky, leads to a basic no-homomorphism lemma. According to this definition, a signed graph (G, σ) admits a homomorphism to a signed graph (H, π) if there is a mapping φ from the vertices and edges of G to the vertices and edges of H (respectively) which preserves adjacencies, incidences, and signs of closed walks (i.e., the product of the sign of their edges). For ij = 00, 01, 10, 11, let g ij (G, σ) be the length of a shortest closed walk of (G, σ) which is, positive and of even length for ij = 00, positive and of odd length for ij = 01, negative and of even length for ij = 10, negative and of odd length for ij = 11. For each ij, if there is no closed walk of the corresponding type, we let

In this case, g 10 (G, σ) is certainly realized by a cycle of G, and it will be referred to as the unbalanced-girth of (G, σ).

It then follows that if (G, σ) admits a homomorphism to (H, π), then g ij (G, σ) ≥ g ij (H, π) for ij ∈ {00, 01, 10, 11}.

Studying the restriction of homomorphisms of signed graphs on sparse families, in this paper we first prove that for any given signed graph (H, π), there is a positive value of such that, if G is a connected graph of maximum average degree less than 2 + , and if σ is a signature of G such that g ij (G, σ) ≥ g ij (H, π) for all ij ∈ {00, 01, 10, 11}, then (G, σ) admits a homomorphism to (H, π).

For (H, π) being the signed graph on K 4 with exactly one negative edge, we show that = 4 7 works and that this is the best possible value of . For (H, π) being the negative cycle of length 2g, denoted U C 2g , we show that = 1 2g-1 works. As a bipartite analogue of Jaeger-Zhang conjecture, it was conjectured in [14] that every signed bipartite planar graph (G, σ) satisfying g ij (G, σ) ≥ 4g -2 admits a homomorphism to U C 2g . We show that 4g -2 cannot be strengthened, and, supporting the conjecture, we prove it for (G, σ) satisfying the weaker condition g ij (G, σ) ≥ 8g -2.

In the course of our work, we also provide a duality theorem to decide whether a 2-edge-colored graph admits a homomorphism to a certain class of 2-edge-colored signed graphs or not.

Introduction

One of the earliest observations in the theory of (proper) vertex coloring of graphs is that if every subgraph of a graph G has a vertex of degree at most k, then G is (k+1)-colorable. Many efforts are devoted to improve, generalize, and strengthen this early observation. Brook's theorem is one such result which classifies the case when k + 1 colors are actually needed. The four color theorem could also be seen as an improvement as, by Euler's formula, there is a vertex of degree at most five in every planar graph, and thus the trivial bound of 6 is decreased to 4. So is Grötzsch's theorem, as every triangle-free planar graph has a vertex of degree at most 4, and is thus 5-colorable, but the theorem decreases this bound to 3.

Further studies and recent developments are based on notions such as minor, maximum average degree of graph, denoted mad(G), various coloring notions such as circular and fractional coloring, and more generally the notion of graph homomorphism.

Considering the general notion of homomorphisms of graphs (see [START_REF] Hell | Graphs and Homomorphisms[END_REF] for a comprehensive book on this topic), the following is easily observed (we denote by C n the cycle of order n).

Lemma 1. There exists a homomorphism of C 2 +1 to C 2k+1 if and only if ≥ k.

Therefore, if there is a homomorphism of G to H, then the odd-girth of G (length of a shortest odd cycle in G) is at least the odd-girth of H. This provides an easy condition upon which one can guarantee the non-existence of a homomorphism of G to H. While this condition is not always sufficient, under certain conditions it might be. Some of the well-known coloring results or conjectures in graph theory can be viewed in this context. A notable example is the following conjecture, whose first case, and the only case proven so far, is Grötzsch's theorem.

Conjecture 2 (Jaeger-Zhang [START_REF] Zhang | Circular flows of nearly Eulerian graphs and vertex-splitting[END_REF]). Every planar graph of odd-girth 4k +1, k ≥ 1, admits a homomorphism to C 2k+1 .

For required definitions we refer to Section 2, but we would like to note that the same conjecture with a girth condition rather than an odd-girth condition is the dual statement of a conjecture of Jaeger dealing with flows on graphs, when restricted to the class of planar graphs. That the girth condition can be relaxed to a condition on the odd-girth is proposed by C.Q. Zhang. The folding lemma of W. Klostermeyer and C.Q. Zhang [START_REF] Klostermeyer | 2 + ε)-coloring of planar graphs with large odd girth[END_REF] is supporting evidence of this suggestion and implies a similar condition on the average degree. For partial results in this context we refer to [START_REF] Cranston | An introduction to the discharging method via graph coloring[END_REF].

Results of this type can normally be rephrased in the following general framework: "Given a non bipartite graph H, any sufficiently enough sparse graph G either admits a homomorphism to H, or has a small odd cycle".

For each specific problem, working on a given family of graphs (such as planar graphs, or any minor-closed class of graphs) and with a fixed H or a fixed family of H's, one would like to know precisely "how sparse is enough". For a specific conjecture in this regard when H is just an odd cycle and some related questions we refer to [5, Section 2].

A notion of graph theory which provides room for extensions and strengthening of classical graph theory results is the notion of signed graph. This notion, among others, provides a stronger and more natural connection between theories of minors and coloring. Using this notion, colorings and homomorphisms of (signed) bipartite graphs are no longer a matter of triviality. Indeed, as we will describe later, the notion of homomorphism restricted to signed bipartite graphs captures the classical theory of homomorphisms of graphs.

In this work, we initiate the study of coloring and homomorphism problems for sparse signed graphs, with particular emphasis on the bipartite case. Among other things, we provide partial results supporting the bipartite analogue of Jaeger-Zhang conjecture proposed in [START_REF] Naserasr | Homomorphisms of signed graphs[END_REF].

Notation and terminology

Graphs are finite and simple, i.e., without loops and without parallel edges. For classical graph theory we use the standard notation, mainly following [START_REF] Bondy | Graph Theory[END_REF].

The main objects of this study are signed graphs. As the theories on signed graphs are under development from a wide range of interests, there are some differences in terminology in the existing literature. In this paper we adopt an improved notation introduced in [START_REF] Naserasr | Homomorphisms of signed graphs: An update[END_REF] which fits well with respect to the theory of homomorphisms and matches most other views (compared to the recent introduction of the theory in [START_REF] Naserasr | Homomorphisms of signed graphs[END_REF]). We start with basic notation of graphs for clarity.

A graph is an ordered pair G = (V, E) where V is a set, which usually and certainly in this paper, is finite, and E is a collection of 2-subsets of V (E could be considered as a multiset when we speak of a multigraph). Elements of V are referred to as vertices and elements of E are edges. Thus, using this definition, we do not allow loops. The sets V and E can also be denoted as V (G) and E(G), respectively.

We follow the standard terminology of graphs. Some points are as follows. A vertex of degree k may be referred to as a k-vertex. A walk of length k in a graph G is a sequence of (not necessarily distinct) vertices v 0 . . . v k , such that v i v i+1 is an edge in G for every i, 0 ≤ i < k. If v 0 = v k , we say the walk is a closed walk. A path is a walk with the additional property that no vertex appears twice. A closed walk where the first vertex is the only repeated vertex is a cycle.

A thread is a path whose internal vertices are all of degree 2 in G. If x and y are the end vertices of the walk, the path or the thread, we call it an xy-walk, xy-path or xy-thread, respectively. Observe that every edge in G is a walk, a path, and a thread of length 1.

A 2-edge-colored graph is a graph whose edges are assigned one of the two possible colors (this coloring is not necessarily proper). Assuming E 1 and E 2 are the color classes, we will denote the corresponding 2-edge-colored graph by a triplet, namely (V, E 1 , E 2 ) or (G, E 1 , E 2 ), in order to distinguish it from a signed graph. As for graphs, the sets E 1 and E 2 can also be denoted E 1 (G) and E 2 (G), respectively.

A signed graph is a graph G together with an assignment of one of the two possible signs (we mean + or -) to each edge of G. This notion is thus different from that of a 2-edge-colored graph, since {+, -} is treated as a 2-element multiplicative group with + and -playing the roles of +1 and -1, respectively, and with the usual multiplication as operation, which allows us to speak of positive or negative objects (e.g. subgraphs), using the operation of this group.

One may then use one of the two natural notations to denote a signed graph, namely either (G, σ), with σ being the function that assigns signs to edges, or (G, Σ), with Σ being the set of negative edges. We mainly use the former one in this paper.

One notion of importance, which distinguishes signed graphs from 2-edge-colored graphs, is the notion of switching (also called resigning by some authors). Given a set X of vertices of a signed graph (G, σ), switching the set X consists of multiplying all edges of the edge cut [X, V (G) \ X] by the negative sign, in other words, it is switching the sign of each edge with exactly one end in X. If X = {x} is a singleton, we will say that we switch x rather than X. It is then easy to observe that switching a set X is equivalent to switching all vertices of X, or switching all vertices of V (G) \ X.

Let u and v be two (not necessarily distinct) vertices of a signed graph (G, σ), and W be a uv-walk in G (recall that edges can be used more than once in a walk). The sign of such a walk is simply the product of the sign of its edges, each edge appearing more than once being counted with the corresponding multiplicity.

Observe that switching an internal vertex of a walk does not change the sign of the walk. Thus, the sign of a closed walk is invariant under the operation of switching. However, if W is a non-closed walk, then switching exactly one of its ends will change the sign of W .

Together with the parity of length, this leads to four distinguishable types of closed walks: positive and of even length (type 00), positive and of odd length (type 01), negative and of even length [START_REF] Klostermeyer | 2 + ε)-coloring of planar graphs with large odd girth[END_REF], negative and of odd length (type 11). This type notation is convenient in the following sense: if W 1 is a closed walk of type ab starting at u and W 2 is a closed walk of type cd also starting at u, then the uw-walk W 1 ∪ W 2 , obtained by concatenating W 1 and W 2 , is of type ab + cd (where the addition is taken in the additive group Z 2 × Z 2 ).

A positive cycle is said to be balanced, whereas a negative cycle is said to be unbalanced. An unbalanced cycle of length is denoted by U C .

Structures whose sign is invariant under switching, especially closed walks, are the key to our study of homomorphisms. Two signatures σ 1 and σ 2 of the same graph G are said to be equivalent if one can be obtained from the other by a switching. It is easily observed that this induces an equivalence relation on the class of all signatures on G. For each family of equivalent signatures, the set of balanced cycles is fixed. A key lemma of Zaslavsky is that the converse is also true, i.e., the set of balanced cycles uniquely determines the equivalent classes of signatures.

Lemma 3 (Zaslavsky [START_REF] Zaslavsky | Signed graphs[END_REF]). Given two signatures σ 1 and σ 2 of a graph G, σ 1 is a switching of σ 2 if and only if the sets of balanced (or, equivalently, unbalanced) cycles of (G, σ 1 ) and (G, σ 2 ) are the same.

We may now define the key notions of this work: homomorphisms of graphs, of 2-edgecolored graphs and of signed graphs. We emphasize on the difference between homomorphisms of 2-edge-colored graphs and of signed graphs, but we will indeed take advantage of the strong relation between these two notions when proving our results. Definition 4. Given two graphs G and H, a homomorphism of G to H is a mapping φ which maps vertices of G to vertices of H and edges of G to edges of H, in such a way that adjacencies and incidences are preserved, i.e., φ(x)φ(y) ∈ E(H) whenever xy ∈ E(G), and φ(x) ∈ φ(e) (in H) whenever x ∈ e (in G).

If G and H are both 2-edge-colored graphs, then a homomorphism of G to H is a homomorphism φ of the underlying (uncolored) graphs which preserves the colors as well, i.e., φ(e) ∈ E 1 (H) if and only if e ∈ E 1 (G).

Given signed graphs (G, σ) and (H, π), a homomorphism of (G, σ) to (H, π) is a homomorphism of G to H which preserves the balance of all closed walks, i.e., the image of a closed walk W in (H, π) is positive if and only if W is a positive closed walk in (G, σ).

In the three definitions above, if the underlying graphs are simple (which will be the case in this study), then we can define a homomorphism to be a mapping of vertices which preserves adjacency. For 2-edge-colored graphs, we require furthermore that the mapping preserves the color of edges and, for signed graphs, we require that the mapping preserves the signs of closed walks. Next we show a strong connection between these two conditions. Theorem 5. A signed graph (G, σ) admits a homomorphism to a signed graph (H, π) if and only if there is a switching (G, σ ) of (G, σ) and a homomorphism of G to H which preserves the sign of the edges with respect to σ and π.

One direction of this theorem is easy, since a sign preserving mapping of (G, σ ) to (H, π) certainly preserves the signs of closed-walks and these signs are the same in (G, σ) and (G, σ ). On the other hand, if there is a homomorphism φ of (G, σ) to (H, π), defining σ (e) = π(φ(e)) we get a signature σ which induces the same sign as σ on all closed walks. Thus, by Lemma 3, σ is a switching of σ.

We note that one can then take the condition of this theorem as the definition of homomorphisms of signed graphs. This is indeed the original definition given in [START_REF] Naserasr | Homomorphisms of signed graphs[END_REF], and in the rest of this work we will use this definition. Thus a homomorphism of a signed (simple) graph (G, σ) to (H, π) will be denoted as an ordered pair of functions f = (f 1 , f 2 ), with f 1 : V (G) → {+, -} and f 2 : V (G) → V (H), where for each vertex x of G, f 1 specifies whether x is switched or not (according to whether f 1 (x) = + or -, respectively) and f 2 specifies to which vertex of V (H) the vertex x is mapped.

A rather surprising result of [START_REF] Naserasr | Homomorphisms of signed graphs[END_REF] is that the restriction of homomorphisms on signed bipartite graphs captures the classic notion of homomorphisms of graphs as a special case. This is shown through the following construction. Given a graph G, let S(G) be the signed bipartite graph built as follows. For each edge uv of G, first add a parallel edge, and then subdivide both edges in order to form a 4-cycle (if G has n vertices and m edges, then S(G) has n + 2m vertices and 4m edges). Finally, for each such 4-cycle, we assign one negative and three positive signs to its edges. With this construction in mind, the following is proved in [START_REF] Naserasr | Homomorphisms of signed graphs[END_REF].

Theorem 6 (Naserasr, Rollová and Sopena [START_REF] Naserasr | Homomorphisms of signed graphs[END_REF]). For every two graphs G and H, there is a homomorphism of G to H if and only if there is a homomorphism of S(G) to S(H).

It is thus of special interest to study the homomorphism relation on the subclass of signed bipartite graphs.

A common notion in the theory of homomorphisms is the notion of core which is defined analogously for each of the structural objects. A core is a graph (analogously, a Figure 1: Signed graphs where g ij is given by a closed walk which is not a cycle. signed or a 2-edge-colored graph) which does not admit any homomorphism to any of its proper subgraphs. The core of a graph G is then the smallest subgraph of G (with respect to subgraph inclusion) to which G admits a homomorphism. It is not difficult to show, in each case, that the core of a graph is unique up to isomorphism [START_REF] Hell | Graphs and Homomorphisms[END_REF].

An automorphism of a signed graph (G, σ) is a homomorphism of (G, σ) to itself which is one-to-one. A signed graph is vertex transitive if, for each pair x, y of vertices, there is an automorphism which maps x to y. The most important examples of vertex transitive signed graphs for this work are unbalanced cycles.

Girth and maximum average degree conditions

An advantage of the new definition of homomorphisms of signed graphs is an immediate no-homomorphism lemma which is based on the following definition. Definition 7. Given a signed graph (G, σ) and ij ∈ Z 2 2 , the ij-closed-walk-girth of (G, σ), denoted g ij (G, σ), is the length of a shortest closed walk of type ij in (G, σ). When there is no such closed walk, we let g ij (G, σ) = ∞.

Observe that g 00 (G, σ) = 2 unless G has no edges, in which case g 00 (G, σ) = ∞. We note that g ij (G, σ) for ij = 00 might not be realized by a cycle of G as shown by examples of Figure 1. However, it can be shown that for each signed graph (G, σ), at most one of the values g ij , ij = 00, can be realized by a closed walk which is not a cycle, and that can only be the largest of the three values. Indeed, suppose that g ij is realized by a closed walk W which is not a cycle. In that case, some vertex x necessarily appears (at least) twice in W . Split then W into two closed walks W 1 and W 2 at x. Observe that for i j = ij and i j = 00, exactly one of the closed walks W 1 , W 2 is of type i j . This shows that if g ij is realized by a closed walk which is not a cycle, then it is strictly larger than the other two values.

Furthermore, as shown in [START_REF] Naserasr | Homomorphisms of signed graphs: An update[END_REF], in a connected signed graph (G, σ), among the three values g 01 (G, σ), g 10 (G, σ) and g 11 (G, σ), we cannot have exactly one value being ∞. This leads to three special subclasses where exactly two of the values are ∞. Among these three cases, the case g 01 (G, σ) = g 11 (G, σ) = ∞ corresponds to the class of signed bipartite graphs, which is of special interest for this work.

We now state a basic no-homomorphism lemma for signed graphs.

Lemma 8. If a signed graph (G, σ) admits a homomorphism to a signed graph (H, π),

then g ij (G, σ) ≥ g ij (H, π) for each ij ∈ Z 2 2 .
It is easy to observe that the conditions g ij (G, σ) ≥ g ij (H, π) for each ij ∈ Z 2 2 are not sufficient for (G, σ) to admit a homomorphism to (H, π). However, as we will show in this work, for graphs of small maximum average degree, these conditions are also sufficient. The bound on the maximum average degree will be provided as a function of (H, π). This is stated more precisely in the next theorem, but we first recall a folklore lemma on the structure of graphs with small maximum average degree [START_REF] Cranston | An introduction to the discharging method via graph coloring[END_REF].

Lemma 9. If G is a connected graph with minimum degree at least 2 and maximum average degree less than 2 + 2 3d-1 , then either G is a cycle or G contains a thread of length d.

Theorem 10. For every connected signed graph (H, π), there exists an such that, for each graph G with mad(G) < 2 + , and any signature σ on G such that

g ij (G, σ) ≥ g ij (H, π) for each ij ∈ Z 2 2 , (G, σ) → (H, π). Proof.
To prove Theorem 10, one may first observe that vertices of degree 0 or 1 are of no importance. Thus, by Lemma 9, either G is a cycle or it contains a long thread.

If G is a cycle, then (G, σ) is a cycle of type, say, ij. As g ij (G, σ) ≥ g ij (H, π), this cycle can be mapped to a walk of type ij in (H, π). Therefore, by Lemma 9, we may assume that G has a thread of length d where d is a function of which increases when tends to zero.

For the remaining part of the proof we assume

g ij (H, π) < ∞ for all ij ∈ Z 2 2 .
The other cases are similar and simpler, since in each case one may consider (H, π) to be just a cycle and then apply a simpler version of the following arguments. Recall that diam(H) is the largest possible distance between two vertices of H. Since H is a connected graph, this is a finite number and a function of H.

Take an integer d ≥ 2diam(H) + max{g ij (H, π)} and, using Lemma 9, choose an so that mad(G) < 2 + implies the existence of a thread P of length d in G. Let x and y be the two ends of this thread and consider the signed graph (G , σ ) obtained from (G, σ) by removing the internal vertices of P .

We may map (G , σ ) to (H, π) by induction. Let φ be such a homomorphism. We would like to extend φ to a homomorphism of (G, σ) to (H, π). We pay attention that x and y are already mapped and we are not allowed to switch these two vertices, but we are allowed to switch internal vertices of P after which we may choose where to map them. Recall that switching any internal vertex of P does not change the sign of P . Furthermore, since the parity of P is given, employing the terminology of types of closed walks, we may say P is of type ij for some ij ∈ Z 2 2 . We may now consider a shortest path Q in (H, σ) connecting φ(x) and φ(y). If Q is of the same type as P , then we map P to Q, which is possible because the parity and sign of P permits this. Otherwise, we choose a shortest closed walk W of type i j starting at a vertex v of Q such that the walk Q , starting from φ(x), going to v on the path Q, then traversing W , and then moving to φ(y) on the path Q, is of the same type as P . Since we have assumed that (H, π) contains closed walks of each type, and since H is connected, this is possible. Furthermore, by taking a shortest path and a shortest closed walk, we have ensured that Q has length at most d. Therefore, we may now extend the homomorphism φ to a homomorphism of P to Q .

A challenging question is then to determine the best value of for a given (H, π). This value may be improved by further restriction on the graph (G, σ). For example what if we consider only planar graphs? Note that planarity already imposes the condition of maximum average degree being less than 6. Further conditions on lengths of facial cycles of a planar graph may improve this bound on the average degree. A sort of dual question is the following one, which is of high interest. For c 10 = 10 = 4, c 11 = 11 = c 01 = 01 = 3, while a lower bound of 10 on the order of H is given in [START_REF] Naserasr | Homomorphisms of signed graphs[END_REF], an upper bound of 40 is proved in [START_REF] Ochem | Homomorphisms of 2-Edge-Colored Triangle-Free Planar Graphs[END_REF]. Moreover, the authors of [START_REF] Ochem | Homomorphisms of 2-Edge-Colored Triangle-Free Planar Graphs[END_REF] ask whether 10 could be the optimal upper bound or not, and propose a specific signed graph of order 10 as a candidate.

Problem 11. Given integers c ij and ij , ij ∈ {01, 10, 11}, satisfying c ij ≥ ij for every ij, what is a smallest signed graph (H, π) with g ij (H, π) ≥ ij such that every planar signed graph (G, σ) with g ij (G, σ) ≥ c ij
The main results of this work can then be seen as providing optimal values in Theorem 10 for specific cases. More precisely, we prove in Section 6 the following result.

Theorem 12. If G is a graph with mad(G) < 18 7 then, for every signature σ on G, (G, σ) → (K 4 , {e}). Moreover, the bound of 18 7 is best possible. In Section 7, studying the case of signed bipartite graphs, we prove the following theorem.

Theorem 13. If G is a bipartite graph with mad(G) < 2+ 1 2g-1 then, for every signature σ on G such that g 01 (G, σ) ≥ 2g, (G, σ) → U C 2g .
Furthermore, as a bipartite analogue of Jaeger-Zhang conjecture, the following conjecture was proposed in [START_REF] Naserasr | Homomorphisms of signed graphs[END_REF], for which we will provide some supporting results. Recall that, when G is bipartite, g 10 (G, σ) is called the unbalanced-girth of (G, σ).

Conjecture 14 (Naserasr, Rollová and Sopena [START_REF] Naserasr | Homomorphisms of signed graphs[END_REF]). Every signed bipartite planar graph (G, σ) of unbalanced-girth at least 4g -2 admits a homomorphism to U C 2g .

The rest of the paper is organized as follows. In the next section, we provide a duality theorem for mapping 2-edge-colored graphs to (C 2g , {e}, E -e). In Section 5, we prove some properties of minimum counterexamples for our statements. We prove Theorem 12 in Section 6, and Theorem 13 in Section 7. In Section 8, applying our results on planar graphs, we provide some support for Conjecture 14. Finally, in Section 9, we give some examples proving that the upper bounds on some of our results and conjectures are the best possible (in the case of conjectures, if possible at all).

A duality theorem for homomorphisms to a 2-edgecolored cycle

By recent proofs of the dichotomy conjecture of Feder-Vardi [START_REF] Feder | The computational structure of monotone monadic SNP and constraint satisfaction: a study through datalog and group theory[END_REF], for every 2-edge-colored graph H, the H-coloring problem is either polynomial time or NP-hard. Among the polynomial time solvable cases, one is when H is (C 2g , {e}, E -{e}). Here we will give a duality theorem which in particular will imply that (C 2g , {e}, E -{e})-coloring is polynomial time solvable. For more on this subject we refer to [START_REF] Brewster | Vertex colourings of edge-coloured graphs[END_REF][START_REF] Brewster | The complexity of signed graph and edge-coloured graph homomorphisms[END_REF]. A polynomial time algorithm for this is also given in [START_REF] Brewster | Vertex colourings of edge-coloured graphs[END_REF], but our interest is in theoretical applications of the simple and nice duality theorem which we provide here. Let (P n+1 , {e 1 , e n }, E -{e 1 , e n }) be a path of length n whose first and last edges are colored red (or 1), while all other edges are colored blue (or 2). It is easily observed that there exists a homomorphism of this 2-edge-colored graph to the 2-edge-colored cycle (C 2g , {e}, E -{e}) if and only if either n is even, or n is odd and n ≥ 2g + 1. Therefore, if a 2-edge-colored graph (G, E 1 , E 2 ) admits a homomorphism from (P 2 -1 , {e 1 , e 2 -1 }, E -{e 1 , e 2 -1 }), with ≤ g, then it does not admit any homomorphism to (C 2g , {e}, E -{e}). Our claim is that this necessary condition is also sufficient for an input whose underlying graph is bipartite.

Theorem 15. Given a bipartite graph G, a 2-edge-colored graph (G, E 1 , E 2 ) admits a homomorphism to (C 2g , {e}, E -{e}) if and only if there is no homomorphism of (P 2g-1 , {e 1 , e 2g-1 }, E -{e 1 , e 2g-1 }) to (G, E 1 , E 2 ).
Proof. Observe that for every i, i ≤ g, (P 2i-1 , {e 1 , e 2i-1 }, E-{e 1 , e 2i-1 }) and (C 2i , {e}, E-{e}) are both homomorphic images of (P 2g-1 , {e 1 , e 2g-1 }, E -{e 1 , e 2g-1 }). Moreover, any bipartite image of (P 2g-1 , {e 1 , e 2g-1 }, E-{e 1 , e 2g-1 }) must contain either (P 2i-1 , {e 1 , e 2i-1 }, E-{e 1 , e 2i-1 }) or (C 2i , {e}, E -{e}) as a subgraph for some i ≤ g.

Thus (G, E 1 , E 2 ) does not admit any homomorphism from (P 2g-1 , {e 1 , e 2g-1 }, E -{e 1 , e 2g-1 }) if and only if it contains neither (P 2i-1 , {e 1 , e 2i-1 }, E-{e 1 , e 2i-1 }) nor (C 2i , {e}, E-{e}) as a subgraph, for every i ≤ g. In other words, (G, E 1 , E 2 ) does not admit any homomorphism from (P 2g-1 , {e 1 , e 2g-1 }, E -{e 1 , e 2g-1 }) if and only if no two vertices, each incident with a red edge, are connected by a blue path of odd length 2 + 1 where < g. In particular, this implies that (C 2g , {e}, E -{e}) does not admit any homomorphism from (P 2g-1 , {e 1 , e 2g-1 }, E -{e 1 , e 2g-1 }), which proves the "only if" part of our theorem.

For the converse, denote by x 0 y 0 x 1 y 1 . . . x g-1 y g-1 the cycle C 2g and assume x 0 y 0 is the red edge of (C 2g , {e}, E -{e}). Consider a 2-edge-colored graph (G, E 1 , E 2 ), where G is a bipartite graph with bipartition (X, Y ) and such that (

P 2g-1 , {e 1 , e 2g-1 }, E -{e 1 , e 2g-1 }) does not admit a homomorphism to (G, E 1 , E 2 ). We need to find a homomorphism of (G, E 1 , E 2 ) to (C 2g , {e}, E -{e}). Let X 0 (respectively Y 0 ) be vertices in X (respectively Y ) each of which is incident with a red edge. Let X i , 1 ≤ i ≤ g -2, be the set of vertices in X at distance i from X 0 ∪ Y 0 . Thus a vertex v of X is in X i if a closest vertex to it in X 0 ∪ Y 0 , say f (v), is at distance i from it.
Observe that, because of the bipartition of G, for odd values of i, f (v) is in Y 0 and for even values of i, f (v) is in X 0 . Let X g-1 be all the remaining vertices in X, thus vertices in X g are at distance g -1 or more from all vertices in X 0 ∪ Y 0 . We similarly define Y i , i ≤ g -1.

We may now define a homomorphism of (G, E 1 , E 2 ) to (C 2g , {e}, E -{e}) as follows: all vertices in X i are mapped to the vertex x i and all vertices in Y i are mapped to the vertex y i . It remains to show that red edges of (G, E 1 , E 2 ) (edges in E 1 ) are mapped to red edges of (C 2g , {e}, E -{e}) (the edge e = x 0 y 0 ) and that blues edges are mapped to blue edges. A red edge in (G, E 1 , E 2 ) must have, by definition and because of the bipartition, one end in X 0 and the other end in Y 0 . Thus it maps to x 0 y 0 which is the red edge of (C 2g , {e}, E -{e}). Let e = uv be a blue edge, and assume u ∈ X i , i < g -1.

Let f (u) be a closest vertex in X 0 ∪ Y 0 to u. Recall that whether f (u) is in X 0 or in Y 0 only depends on the parity of i. Observe that v is a vertex in the Y part of G because of the bipartition of G. We claim that v cannot be in Y i . Otherwise, f (v), a closest vertex to v in X 0 ∪ Y 0 , and f (u) must be in distinct parts. Then the walk composed of a shortest connection from f (u) to u, the edge uv and a shortest connection from v to f (v), fits the parity condition to be the image of (P 2g-1 , {e 1 , e 2g-1 }, E -{e 1 , e 2g-1 }), but this path cannot map to (G, E 1 , E 2 ). Thus, considering the triangle inequality, the vertex v has to be either in Y i-1 or in Y i+1 . Since both y i-1 x i and x i y i+1 are blue edges of (C 2g , {e}, E -{e}), uv is mapped to a blue edge and this type of edges are fine as well. It only remains to consider a blue edge uv where u ∈ X g-1 . In this case, again by the triangle inequality, either v ∈ Y g-2 or v ∈ Y g-1 , since y g-2 x g-1 and x g-1 y g-1 are both blue edges of (C 2g , {e}, E -{e}), and we are done with this case as well.

In relation to signed graph homomorphisms, we observed that every unbalanced cycle can be switched in such a way that it contains a single negative edge. Therefore, the question of deciding whether a signed bipartite graph admits a homomorphism to an unbalanced cycle U C 2g amounts to finding an equivalent signature which does not induce a (P n+1 , {e 1 , e n }, E -{e 1 , e n }) structure.

However, unless P = N P , this would not be an easy task as it is shown in [START_REF] Brewster | The complexity of signed graph and edge-coloured graph homomorphisms[END_REF][START_REF] Foucaud | The complexity of homomorphisms of signed graphs and signed constraint satisfaction[END_REF] that this homomorphism question, in contrast to its 2-edge-colored counterpart, is an NP-complete problem.

As an application of Theorem 15, we have the following result.

Minimal elements

A standard technique to prove results of the type we consider in this work is to consider a minimum counterexample, prove some properties that such a graph must satisfy, and finally derive a contradiction. The minimality of such a counterexample can be viewed in two ways. The first one is to say that no subgraph of our minimal counterexample is a counterexample, which, in particular, says that a minimal counterexample is a core. The second one is to say that no smaller member of the class of graphs we are working with is a counterexample. This, in particular, implies that no (proper) homomorphic image of our minimal counterexample belongs to the considered class of graphs.

In view of the former case, i.e., a minimum counterexample necessarily being a core, we will show here that certain subdivisions of K 4 cannot be a core. In view of the latter case, Klostermeyer and Zhang developed in [START_REF] Klostermeyer | 2 + ε)-coloring of planar graphs with large odd girth[END_REF] a so-called "folding lemma" for homomorphism problems on the class of planar graphs, which implies that every planar graph of odd-girth 2k + 1 has a planar homomorphic image for which, in every planar embedding, every face is a (2k + 1)-cycle. An analogue of this lemma for the class of signed bipartite planar graphs is developed in [START_REF] Naserasr | Homomorphisms of planar signed graphs to signed projective cubes[END_REF], which would also be of importance for the part of our work which deals with this subclass of signed graphs. We thus restate this lemma and its corollary below.

Lemma 17 (Naserasr, Rollová and Sopena [START_REF] Naserasr | Homomorphisms of planar signed graphs to signed projective cubes[END_REF]). Let (G, σ) be a signed bipartite graph of unbalanced-girth 2g, together with a planar embedding. If (G, σ) has a facial cycle C which is not an unbalanced cycle of length 2g, then there exist two vertices x and y of C, at distance two from each other, such that the planar signed graph obtained from (G, σ) by identifying x and y is a homomorphic image of (G, σ) with unbalanced-girth 2g.

Corollary 18. Every signed planar bipartite graph of unbalanced-girth 2g admits a planar homomorphic image of unbalanced-girth 2g where, in every planar embedding, every face is an unbalanced cycle of length exactly 2g. Thus, for instance, a minimal counterexample to Conjecture 14 should be a signed bipartite planar graph such that every facial cycle of any of its planar embeddings is an unbalanced cycle of length exactly 4g -2.

A subdivision of K 4 is a graph obtained by replacing some or all edges of K 4 by threads connecting their end points. A signed subdivision of K 4 is any signed graph based on a subdivision of K 4 . A planar drawing of a subdivision of K 4 has four facial cycles. As the number of unbalanced faces must be even (since each negative edge changes the balance of two incident faces), there are essentially three different types of signed subdivisions of K 4 , namely those having two, four, or no unbalanced faces. We are interested in the case where the number of unbalanced faces is four, and we want to determine when such a signed subdivision of K 4 is a core. The next two lemmas give an answer to this question for two particular cases, and will be used in Section 7 to prove Theorem 13.

Let -----K 4 be a subdivision of K 4 whose (main) vertices are a, b, c and d (see Figure 2). For every x, y ∈ {a, b, c, d}, x = y, let P xy be the path which represents the edge xy, and let xy be the length of P xy . Moreover, let C xyz = P xy + P yz + P zx .

In [START_REF] Naserasr | Cores of subdivisions of K 4[END_REF], all subdivisions of K 4 which are cores are classified. The following case of that result is used in this work.

Lemma 19. If

-----K 4 is a bipartite subdivision of K 4 such that |C abc | = 2g and ad + bd + cd ≥ 4g, and σ is a signature of -----K 4 such that C abc is an unbalanced cycle and ( -----K 4 , σ) is of unbalanced-girth 2g, then the core of ( -----

K 4 , σ) is U C 2g .
Let K ++ 3 be the multigraph obtained from K 3 , with vertices a, b and c, by adding a parallel edge to each of the edges ab and ac. Similarly to the proof of the previous lemma, we can prove the following result which claims that certain signed graphs, build upon specific subdivisions of K ++ 3 (see Figure 3) are not cores. The following has also been proved in [START_REF] Naserasr | Cores of subdivisions of K 4[END_REF]. such that the outer cycle is of length 2g and the total length of the three threads incident to b is at least 4g, and σ is a signature of --------

K ++ 3 such that ( -------- K ++ 3 , σ) is of unbalanced-girth 2g, then the core of ( -------- K ++ 3 , σ) is U C 2g .
6 Mapping sparse signed graphs to (K 4 , {e})

In this section, we prove Theorem 12, using standard discharging technique. A reducible configuration for this theorem is a signed graph (F, σ 1 ) with the following property: given any signed graph (G, σ) containing (F, σ 1 ) as a subgraph, every possible homomorphism of the signed graph induced by G -F to (K 4 , {e}) can be extended to a homomorphism of (G, σ) to (K 4 , {e}).

To prove Theorem 12, we first exhibit a set of reducible configurations (Lemmas 24 to 28). Then, to complete the proof, we show that if a graph G has average degree less than 18 7 , then G must contain at least one of these reducible configurations. This will provide a proof of Theorem 12 since we get that a minimum counterexample to the theorem cannot exist.

We start with some notation and terminology. In the rest of this section, (G, σ) is considered to be a minimal counterexample to Theorem12, i.e., a signed graph that does not map to (K 4 , {e}) but such that all its proper subgraphs map to (K 4 , {e}). The main idea is to show that such a graph cannot have average degree smaller than 18 7 . To better state the forbidden configurations we introduce some terminology. Recall that a k-vertex is a vertex of degree k. Furthermore, a 3 i -vertex, i ∈ {0, 1, 2, 3}, is a 3-vertex with exactly i neighbors that are 2-vertices.

We will label the vertices of the signed graph (K 4 , {e}) with V (K 4 ) = {1, 2, 3, 4}, where e = 14 is the negative edge (see Figure 4).

Let (G, σ) be a signed graph. Recall that a mapping φ of (G, σ) to (K 4 , {e}) determines, for each vertex x of (G, σ), whether switching is done at x or not, and to which vertex x has to be mapped. Thus, for each vertex x, φ(x) has one of the eight possible outcomes from the set {±1, ±2, ±3, ±4}. We partition this set of outcomes into four subsets, each of size two, as follows:

C 1 = {+1, +4}, -C 1 = {-1, -4}, C 2 = {+2, +3}, -C 2 = {-2, -3}.
Based on this terminology we have the following facts.

Observation 21. Consider a signed graph (P 2 , σ), where P 2 is the path uv, and suppose that φ(u) = c is fixed. Then, independently of σ, there are three choices for φ(v) for which φ is a homomorphism of (P 2 , σ) to (K 4 , {e}). Moreover, two of these choices belong to some set C i or -C i for some i ∈ {1, 2} and the third belongs either to C 3-i or to -C 3-j .

Observation 22. Consider a signed graph (P 3 , σ), where P 3 is the path uwv, and suppose that φ(u) ∈ C is fixed, where C is one of the sets C i or -C i , for some i ∈ {1, 2}. We then have:

1. If σ(uw)σ(wv) = +, then, for any choice of φ(v) which is not in -C, φ can be extended to a homomorphism of (P 3 , σ) to (K 4 , {e}).

2. If σ(uw)σ(wv) = -, then, for any choice of φ(v) which is not in C, φ can be extended to a homomorphism of (P 3 , σ) to (K 4 , {e}).

Therefore, for any choice of φ(u), we have three pairs of extendable choices for φ(v) and one pair which is not extendable.

Observation 23. Consider a signed graph (T, σ), where T is the tree depicted in Figure 5, and suppose that φ(x ) and φ(y ) are fixed. Then, at least three pairs of colors are available at v for extending φ to a homomorphism of (T, σ) to (K 4 , {e}). Indeed, by Observation 22, each of x and y forbids one pair of colors for u. If they forbid the same pair, then three pairs of colors are available at u, and then every choice is available at v. Otherwise, only two pairs of colors are available at u, and thus three pairs of colors are available at v by Observation 21.

We are now ready to exhibit a set of forbidden configurations.

Lemma 24 (Reducible configuration 1). If every proper subgraph of (G, σ) maps to (K 4 , {e}), but (G, σ) itself does not, then δ(G) ≥ 2.

Proof. Clearly, G cannot contain an isolated vertex. The fact that G cannot either contain a 1-vertex directly follows from Observation 21.

Lemma 25 (Reducible configuration 2). If every proper subgraph of (G, σ) maps to (K 4 , {e}), but (G, σ) itself does not, then G has no pair of adjacent 2-vertices.

Proof. Assume to the contrary that u and v are adjacent 2-vertices in G and let u and v be the other neighbors of u and v, respectively. We claim that every homomorphism φ of the subgraph obtained from (G, σ) by deleting u and v to (K 4 , {e}) can be extended to a homomorphism of (G, σ) to (K 4 , {e}). This follows from the fact that, considering φ(u ), we have five forbidden choices for φ(u) by Observation 21 and, considering φ(v ), we have two forbidden choices for φ(u) by Observation 22, which gives one available color for u.

Lemma 26 (Reducible configuration 3). If every proper subgraph of (G, σ) maps to (K 4 , {e}), but (G, σ) itself does not, then G has no 3 3 -vertex. the three possible choices for φ(v) do not belong to L(v), then it must be the case for some choice

u w v u 1 u 2 w 1 w 1 u w v u 1 w 1 v 2 v 2
φ(u) = c ∈ C 2 .
Now, having made such a choice for φ(u), we know by Observation 22 that u, through the path uu 1 v, forbids two colors for v. Hence, at least one color is still available for v, and thus φ can be extended to a homomorphism of (G, σ) to (K 4 , {e}).

3. {u 1 , u 2 } ∩ {v 1 , v 2 } = ∅.
Let φ be a homomorphism of the subgraph of (G, σ) obtained by deleting the set of vertices {u, v, u 1 , u 2 , v 1 , v 2 } to (K 4 , {e}). By Observation 23, u 1 and u 2 forbid at most one pair of colors for v and, by Observation 22, each of v 1 and v 2 forbids one pair of colors for v. Hence, at least one pair of colors is still available for v, and thus φ can be extended to a homomorphism of (G, σ) to (K 4 , {e}).

This concludes the proof.

Lemma 28 (Reducible configuration 5). If every proper subgraph of (G, σ) maps to (K 4 , {e}), but (G, σ) itself does not, then G has no 3 1 -vertex with two 3 2 -neighbors.

Proof. Let w be 3 1 -vertex adjacent to two 3 2 -vertices, say u and v. Let w 1 be the other neighbor of w, u 1 and u 2 be the 2-neighbors of u, and v 1 and v 2 be the 2-neighbors of v. Let (G , σ ) be the subgraph of (G, σ) obtained by deleting the set of vertices {u, v, w, u 1 , u 2 , v 1 , v 2 , w 1 }. Depending on how many common elements the sets {u 1 , u 2 }, {v 1 , v 2 } and {w 1 } have, we consider the four following cases.

1. Either u 1 = v 1 and u 2 = v 2 , or u 1 = v 1 and u 2 = w 1 (see Figure 8). In both cases the subgraph G is connected to the rest of G by a 2-vertex only, say x (we have either x = w 1 or x = v 2 , respectively). In such a case, the subgraphs (G 1 , σ 1 ) and (G 2 , σ 2 ) of (G, σ) induced by the two connected components G 1 and G 2 of G -x, respectively, each of them admits a homomorphism to (K 4 , {e}), say φ 1 and φ 2 , respectively.

By Observation 22, the color of the neighbor of x in (G 1 , σ 1 ) forbids only one pair of colors for the neighbor of x in (G 2 , σ 2 ). Therefore, by switching all vertices of (G 2 , σ 2 ) if needed (and then replacing each color (+, i) by (-, i), and vice versa, in (G 2 , σ 2 )), the homomorphisms φ 1 and φ 2 can be extended to a homomorphism of (G, σ) to (K 4 , {e}).

u w v u 1 u 2 w 1 v 2 u 2 v 2 w 1
u w v u 1 w 1 v 1 v 2 u 1 v 1 v 2
2. u 1 = v 1 (see Figure 9). In this case, we may assume that u, w, v and u 1 induce an unbalanced 4-cycle, since otherwise we may identify u 1 and w (after having switched u 1 if needed), and get a subgraph of (G, σ) which thus admits a homomorphism to (K 4 , {e}).

By Observation 22, each of u 2 , w 1 and v 2 forbids one pair of colors for u, w and v, respectively. Suppose first that uw is a negative edge, while wv, vu 1 and u 1 u are positive edges. In that case, the 4-cycle (u, w, v, u 1 ) can be colored either (+1, +4, +3, +2), (-1, -4, -3, -2), (+2, -3, -4, +1), or (-2, +3, +4, -1), since no two of these four colorings map the same vertex to the same pair of colors. Now, if the unbalanced 4-cycle (u, w, v, u 1 ) has a different signature, we first switch some of its vertices in such a way that uw becomes the only negative edge, which is possible by Lemma 3. We may then apply the previous argument, combining the switching with the above proposed coloring.

3. u 2 = w 1 (see Figure 10). Note first that, by Observation 22, each of v 1 and v 2 forbids one pair of colors for v, so that two pairs are still available for v. Considering only the edge vw, we get by Observation 21 that each choice of a color for v forbids one pair of colors for w. Moreover, again by Observation 22, u 1 forbids one pair of colors for u. We can now 4. The five vertices u 1 , u 2 , v 1 , v 2 , w 1 are pairwise distinct (see Figure 11).

u w v u 1 u 2 w 1 v 1 v 2 u 1 u 2 v 1 v 2 w 1
In this case, by Observation 23, at most one pair of colors is forbidden for w by the subtree containing u, and another pair of colors is forbidden by the subtree containing v. Finally, by Observation 22, one pair of colors is forbidden for w by w . In total, at most three pairs of colors are forbidden for w and we are done.

This concludes the proof.

Next we prove that every graph with average degree less than 18 7 necessarily contains one of the configurations of the previous lemmas.

Lemma 29. If G is a graph with average degree less than 18 7 , then G contains one of the four following configurations:

C1: an isolated vertex or a 1-vertex, C2: two adjacent 2-vertices,

C3: a 3 3 -vertex, C4: two adjacent 3 2 -vertices, C5: a 3 1 -vertex adjacent to two 3 2 -vertices.
Proof. We prove this statement using the discharging method. Let G be a counterexample to our claim. We give to each vertex v an initial charge of d(v) - 18 7 . Since the average degree of G is less than 18 7 , the total charge is negative. Assuming none of the above configurations exist in G, we will apply two rounds of discharging so that the final charge on each vertex will be nonnegative. This will be a contradiction, thus proving our claim.

The initial charge of each 2-vertex is 2-18 7 = -4 7 , and every other vertex has a positive initial charge (recall that G has minimum degree 2).

For the first round of discharging, we apply the following discharging rule:

(R 1 ) Each vertex of degree at least 3 gives 2 7 to each of its neighbors of degree 2.

Since G has no pair of adjacent 2-vertices, after this round, the charge of each 2-vertex is 0, the charge of each 3 0 -vertex is 3 7 , the charge of each 3 1 -vertex is 1 7 , and the charge of each 3 2 -vertex is -1 7 (recall that G contains no 3 3 -vertex). Moreover, the charge of each k-vertex, k ≥ 4, is at least k - 18 7 -2k 7 = 5k-18 7 ≥ 2 7 . For the second round of discharging, we apply the following discharging rule: (R 2 ) Each 3 2 -vertex receives 1 7 from its unique neighbor which is not a 2-vertex.

Note that this neighbor cannot be a 3 2 -vertex. Therefore, at the end of this round, the final charge of each 3 2 -vertex is 0. It remains to prove that no other vertex will have a negative charge. A 3 1 -vertex has at most one 3 2 -neighbor, so that its final charge is at least 1 7 -1 7 = 0. A 3 0 -vertex gives 1 7 to each of its 3 2 -neighbors, so that its final charge is at least 3 7 -3 7 = 0. Finally, vertices of degree k ≥ 4 have a final charge of at least 5k-18 7

-1 7 = 5k-19 7 ≥ 1 7 .
We are now able to prove Theorem 12. In fact, we prove a slightly stronger version stated below.

Theorem 30. If (G, σ) is a signed graph such that G has average degree less than 18 7 , and every subgraph of (G, σ) obtained by deleting a vertex maps to (K 4 , e), then (G, σ) → (K 4 , e).

Proof. It follows from Lemma 29 and Lemmas 24 to 28 that no counterexample to the theorem exists.

Mapping sparse signed bipartite graphs to unbalanced even cycles

Recall that the study of homomorphisms of signed bipartite graphs captures the study of homomorphisms of graphs as a special case. Hence, the restriction of the study on the class of bipartite graphs is of high interest. In the world of signed bipartite graphs, for (H, π) to admit a homomorphism from any signed bipartite graph (G, σ) with G having maximum average degree less than 2 + , where > 0 depends on H, it is necessary and sufficient for H to have an unbalanced cycle. Here, we prove a slightly stronger version of Theorem 13, stated as follows.

Theorem 31. If (G, σ) is a signed graph such that G is a bipartite graph with average degree less than 2 + 1 2g-1 , the unbalanced-girth of (G, σ) is at least 2g, and every subgraph of (G, σ) obtained by deleting a vertex maps to (C 2g , {e}), then (G, σ) → (C 2g , {e}).

Proof. Note that as a signed graph but not a 2-edge-colored graph, the unbalanced-cycle U C of length is vertex-transitive. Let (G, σ) be a minimum counterexample to the theorem, i.e., G is a bipartite graph, mad(G) < 2 + 1 2g-1 , the unbalanced-girth of (G, σ) is at least 2g, but (G, σ) does not map to U C 2g . Since (G, σ) is of unbalanced-girth at least 2g, and by Lemma 9, G is not just a cycle. Our next conclusion is that G must be 2-connected. Indeed, if this is not the case, then either G has a connected component G 1 which is a proper subgraph, or G has a 2-connected end-block G 2 which is connected to the rest of the graph at a cut-vertex x. By minimality of G, the signed graph induced on G 1 or on G 2 maps to U C 2g . Similarly, if we remove all vertices of G 1 , or if we remove all vertices of G 2 except x, then the induced signed graph also maps to U C 2g . Recall that switching a set X of vertices of any signed graph is the same as switching the complement of X. Since G 2 has only one common vertex with the rest of the graph and G 1 has none, in any homomorphism of the two parts we may choose switchings that coincide on the possible common vertex. Finally, since U C 2g is vertex-transitive, by composing one of the two homomorphisms with an automorphism of U C 2g , we may assume that x is mapped to a same vertex by the two homomorphisms. Hence, they can be composed to a homomorphism of (G, σ) to U C 2g .

The fact that G must be 2-connected implies, in particular, that G has minimum degree at least 2. A 2-vertex is then an internal vertex of a thread. Our next claim is that no such thread can have a length 2g -1 or higher. Assume to the contrary that G has a thread T of length exactly 2g -1, with x and y as its endpoints. Let G be the subgraph obtained by deleting all internal vertices of T and let σ be the signature induced by σ on G . Observe that since G was 2-connected, G is a connected graph. By minimality of (G, σ), the signed bipartite graph (G , σ) maps to U C 2g . Let φ be such a homomorphism. Since G is connected, φ, as a homomorphism of the underlying bipartite graph G to the bipartite graph C 2g , must preserves the bipartition. Thus φ(x) and φ(y) partition U C 2g into two paths of odd length: one containing the negative edge, the other only composed of positive edges. Then, depending on the parity of the number of negative edges of T , and after a suitable switching of its internal vertices, we may extend the homomorphism φ to the vertices of T , thus mapping (G, σ) to U C 2g , which contradicts the choice of (G, σ).

We next consider 3-vertices. Let v be a 3-vertex of G and let x, y and z be the three ends of the threads whose other end is v. Let x , y and z be the corresponding lengths of these threads. We claim that x + y + z ≤ 4g -1. Suppose the contrary and let G be the subgraph obtained from G by removing v and all the internal vertices of the three threads. Let σ be the induced signature on G . By the minimality of G, we have a homomorphism φ = (φ 1 , φ 2 ) of (G , σ ) to U C 2g . Considering the size of the set {φ 2 (x), φ 2 (y), φ 2 (z)}, we have three possible cases.

If this set is of size one, i.e., φ 2 (x) = φ 2 (y) = φ 2 (z), we consider the image of G after applying φ on the subgraph G . The result is then a graph obtained as an unbalanced cycle of length 2g, and the vertex v which is joined to a vertex (φ 2 (x)) of the cycle by three internally vertex disjoint paths of length x , y and z respectively, whose signature is induced by the signature of (G, σ) and φ 1 (x) = φ 1 (y) = φ 1 (z). Among these three paths, two are of a same sign and, since our graph is bipartite, all three of them are of same parity. We can thus map the largest of the two to the smallest one. Noting the this largest thread is not of length greater than 2g, and that the sum of the three lengths was at least 4g, the cycle formed by the two remaining threads between v and φ 2 (x) must be of length at least 2g. We may now use vertex transitivity of U C 2g to complete our mapping as in the previous case.

If |{φ 2 (x), φ 2 (y), φ 2 (z)}| ≥ 2, we similarly use φ to build a homomorphic image of (G, σ), then we show that the image itself can be mapped to U C 2g . To this, we first claim that each facial cycle must be an unbalanced cycle, that is because otherwise we may apply Lemma 17 and reduce the number of faces of this planar image to two, meaning the we have mapped it to U C 2g . In this image, we first apply the switchings given by φ 1 . Next, every two vertices that are identified by the mapping φ 2 are also identified, and no further switching or identification is done. Let (G * , σ * ) be the corresponding image. Since G is connected and φ 2 preserves the bipartition, the image, G * is also bipartite. Furthermore, any cycle using v must use two of the threads incident to it, and thus is of length at least 2g. The only cycle not using v is an unbalanced cycle of length exactly 2g. Depending on whether {φ 2 (x), φ 2 (y), φ 2 (z)} is of size 3 or 2, the signed graph (G * , σ * ) satisfies the conditions of Lemma 19 or Lemma 20 (respectively). Thus, in both cases, (G * , σ * ), and therefore (G, σ), maps to U C 2g .

Finally, to complete the proof, we show that the four conditions of (1) G is 2-connected, (2) G is not cycle (3) G has no thread of length 2g -1 or longer, (4) G has no 3-vertex whose total length of incident threads is larger than 4g -1, would imply that the average degree of G is at least 2 + 1 2g-1 , contradicting our assumption. We use the discharging technique for this step. Assign the degree of each vertex of G as a charge to this vertex. The average charge is then the average degree of G. For each 2-vertex v of G, consider the two ends x v and y v of the thread to which v belongs. Note that x v and y v do exist because G is not a cycle, that x v and y v are distinct, and that they both have degree at least 3 because G is 2-connected (but not a cycle). We then use the following discharging rule. R: Each 2-vertex receives a charge of 1 2(2g-1) from each end of the thread it belongs to.

We claim that after applying this rule, every vertex v has a charge of at least 2 + 1 2g-1 , proving that G has average degree at least this value. We consider three cases, depending on the degree of v.

1. If v is a 2-vertex, then its initial charge is 2. Then, as mentioned above, there are two distinct vertices as the ends of the thread containing v, and each of them gives a charge of 1 2(2g-1) by R. As v does not lose any charge, its final charge is increased to 2 + 1 2g-1 . 2. If v is a 3-vertex, then its initial charge is 3. The vertex v may give a charge of 1 2(2g-1) to each vertex which is on a thread with v as an endpoint. Since the total length of the three threads having v as an end point is at most 4g -1, there are at most 4g -4 such 2-vertices. Therefore, v loses at most (4g -4)

× 1 2(2g-1) = 2g-2 2g-1 , so that its final charge is at least 3 -2g-2 2g-1 = 2 + 1 2g-1 . 3. If v is a k-vertex, k ≥ 4, then its initial charge is k. The vertex v is an endpoint of k
threads, each of length at most 2g -1. Thus, in total, v may give a charge of 1 2(2g-1)

to at most k(2g -2) vertices. Hence, v loses at most k(2g -2) × 1 2(2g-1) = k(g-1) 2g-1 , so that its final charge is at least k -k(g-1)

2g-1 = kg 2g-1 which is greater than 2+

1 2g-1 = 4g-1 2g-1 for k ≥ 4.
Thus, at the end, the charge of every vertex is at least 2 + 1 2g-1 , implying that the average charge, or, equivalently, the average degree, is at least 2 + 1 2g-1 , contradicting our assumption.

The bound on the maximum average degree in the statement of Theorem 31 is not tight. For the case of g = 1, allowing multi-edges, the unbalanced cycle of length 2 is the digon. It is then straightforward to check that any signed bipartite multi-graph maps to U C 2 . For g = 2, while Theorem 31 implies that every signed bipartite graph (G, σ) with no digon maps to U C 4 as long as G has maximum average degree less than 7 3 , an improved and tight bound of 18 7 is proved below. Note that unlike the exceptional case of g = 1, in general case of the theorem we do not consider multi-graphs since any such parallel edges must be of the same sign to satisfy the unbalanced-girth condition, so that the existence of a homomorphism only depends on the underlying simple signed graph.

Theorem 32. If (G, σ) is a signed bipartite graph with mad(G) < 18 7 , then (G, σ) → U C 4 . Furthermore, the bound of 18 7 cannot be improved. Proof. Since mad(G) < 18 7 , and by Theorem 12, (G, σ) maps to (K 4 , {e}). Then, since G is bipartite, by Theorem 16 it also maps to (C 4 , {e}). An example of a bipartite graph with maximum average degree 18 7 which does not map to (C 4 , {e}) is given in Section 9. For larger values of g, i.e., g ≥ 3, we do not know the optimal bound on the maximum average degree for which Theorem 13 would be valid, and leave this as an open question.

One may also consider subclasses of signed bipartite graphs. One subclass of special interest is the class of signed bipartite planar graphs. In Conjecture 14, we have introduced a condition on the unbalanced-girth of signed bipartite planar graphs which may imply the existence of a homomorphism to U C 2g . Using the folding lemma, Lemma 17 or its corollary, Corollary 18, and Euler's formula, this can translate a condition on the average degree. We will show in Section 9 that the proposed bound of this conjecture, if true, is tight.

Application to planar graphs

For the class planar signed graphs, a class of graphs of maximum average degree strictly smaller than 6, the first question is whether there exists or not a signed graph to which every planar signed graph admits a homomorphism. Using techniques developed in [START_REF] Raspaud | Good and semi-strong colorings of oriented planar graphs[END_REF][START_REF] Alon | Homomorphisms of edge-colored graphs and Coxeter groups[END_REF], such a signed graph of order 48 is built in [START_REF] Naserasr | Homomorphisms of signed graphs[END_REF] where a lower bound of 10 on the number of vertices of such a bound is presented as well. The upper bound of 48 is improved to 40 in [START_REF] Ochem | Homomorphisms of 2-Edge-Colored Triangle-Free Planar Graphs[END_REF] where the authors have, furthermore, eliminated all but one graph on 10 vertices as a candidate for a bound on 10 vertices (up to equivalence of signatures). This signed graph is a signed graph on K 10 whose set of negative edges induces a graph on 9 vertices which is isomorphic to the Cartesian product K 3 K 3 . This signed graph on 10 vertices then seems to be a natural candidate and it is tempting to believe that 10 is the right number.

Here we address the problem for planar graphs of large girth, which, combined with Euler's formula, is a translation of the maximum average degree condition for planar graphs. Recall that by Euler's formula, for any connected planar graph G, the relation n -e + f = 2 holds, where n is the number of vertices of G, e is the number of edges of G, and f is the number of faces in a planar embedding of G. For the sake of our study, we may assume that G is 2-connected, which implies that each edge lies exactly on two distinct faces (counting the outer face). If, in a planar embedding of G, each face is of length at least g, then there are at least f g 2 edges in G, or, equivalently, f ≤ 2e g , so that n -e + 2e g ≥ 2. Using the fact that 2e n is the average degree of G, we conclude that the average degree of G is less than 2g g-2 . This proves the following folklore statement. Proposition 33. If G is a 2-connected planar graph with girth at least g, then G has average degree strictly less than 2g g-2 . Since the girth cannot decrease by taking subgraphs, we get that if G is a planar graph with girth at least 9, then G has maximum average degree strictly less than 18 7 . Theorem 12 thus admits the following corollary.

Corollary 34. If G is a planar graph with girth at least 9, and σ is any signature of G, then (G, σ) → (K 4 , e).

Furthermore, considering also Corollary 18, Theorem 32 gives the following corollary.

Corollary 35. If G is a planar bipartite graph, and σ is a signature of G such that the unbalanced-girth of (G, σ) is at least 10, then (G, σ) → U C 4 .

To see that, consider a smallest counterexample (G, σ) to the claim. Then, by Corollary 18, (G, σ) has a planar homomorphic image with unbalanced-girth 10 such that, in all its planar embeddings, every face must be an unbalanced 10-cycle. Moreover, since (G, σ) is a smallest counterexample, this homomorphic image must be (G, σ) itself. Then, by Euler's formula, the graph G has average degree strictly less than 5 2 < 18 7 , and we can thus apply Theorem 32 to get the result.

Using similar arguments, we get that Theorem 13 admits the following corollary.

Corollary 36. If G is a planar bipartite graph, and σ is a signature of G such that the unbalanced-girth of (G, σ) is at least 8k -2, then (G, σ) → U C 2k .

This corollary is in support of Conjecture 14, where we conjecture that having unbalancedgirth at least 4k-2 is enough for a signed bipartite planar graph to admit a homomorphism to U C 2k . If true, then the condition of unbalanced-girth at least 4k -2 is the best possible, as shown by the examples in Section 9.

For the special case of k = 3, Conjecture 14 claims that every planar signed bipartite graph with unbalanced-girth at least 10 admits a homomorphism to U C 6 . Further support for this case, together with connection to the well known Grötzsch's theorem, is as follows. Let G be a triangle-free planar graph, and let ---G be the graph obtained from G by subdividing each edge exactly once. Observe that the result is indeed a planar bipartite graph. Let Σ be a set of edges of ---G such that, for each original edge of G, exactly one of the two corresponding edges in ---G is in Σ. Then, the signed graph ( ---G, σ) is a signed planar bipartite graph with unbalanced-girth 10 because each unbalanced cycle of ( ---G, σ) is a subdivision of and odd-cycle of G and G is assumed to be triangle-free. A homomorphism of G to K 3 , provided by Grötzsch's theorem, can then be extended to a homomorphism of ( ---G, σ) to U C 6 . However, it is not clear whether the case k = 3 of our conjecture would imply Grötzsch's theorem or not. We leave this as an open problem.

Tightness

Consider an unbalanced cycle U C 4 -2 , ≥ 2, whose edges are alternately negative and positive. Consider a bipartition of the underlying cycle into black and white vertices. Now, add a new vertex u joined to each of the black vertices by a path of length 2k -3, k ≥ 2, all of whose edges are positive, and denote by W k, the resulting signed graph. Figure 12 depicts the signed graph W 2,2 . We will prove that for every two integers k, ≥ 2, the signed graph W k, does not map to U C 2k . The proof will use the following lemma.

Lemma 37 (Naserasr, Rollová and Sopena [START_REF] Naserasr | Homomorphisms of signed graphs[END_REF]). For every two unbalanced cycles U C and U C k , U C → U C k if and only if ≥ k and ≡ k (mod 2), and furthermore any such mapping must be onto.

Theorem 38. For every two integers k, ≥ 2, W k, → U C 2k .

Proof. By contradiction, suppose that W k, maps to U C 2k . Then, the unbalanced cycle U C 4 -2 of W k, maps to U C 2k and, by Lemma 37, the corresponding mapping must be onto. Since the underlying graphs of U C 2k and W k, are bipartite and u is a white vertex, u must be identified with a white vertex v of U C 4 -2 . But, for any choice of v, u and v belong to an unbalanced cycle of length 4k -4 and are at distance 2k -2 from each other. Therefore, the identification of u and v produces an unbalanced cycle of length 2k -2, which does not map to U C 2k (since 2k -2 < 2k), contradicting our assumption.

For ≥ k, the signed graph W k, is a planar signed bipartite graph of unbalanced girth 4k -4. This shows that the claim of Conjecture 14, if true, is the best possible.

Moreover, the signed graph W 2,2 , depicted in Figure 12, is a signed bipartite graph with maximum average degree 18 7 which does not map to U C 4 . This proves that the claim of Theorem 32 is best possible.

Corollary 39. There exists a signed bipartite graph with maximum average degree 18 7 which does not map to U C 4 .

Using Theorem 16, it then follows that the claim of Theorem 12 is also best possible.

Corollary 40. There exists a signed graph with maximum average degree 18 7 which does not map to (K 4 , e).

Concluding remarks

This paper is a first work in the study of homomorphisms of sparse signed graphs. A main result here was to show that, given any signed graph (H, π), there exist a positive such that every signed graph satisfying g ij (G, σ) ≥ g ij (H, π) and mad(G) ≤ 2 + maps to (H, π). We determined the optimal value of for (H, π) being (K 4 , e) or (C 4 , e). We believe that a geometric condition such as planarity can help proving parallel results.

This study generalizes various questions from graph coloring. For example, one can define a (H, π)-critical graph to be a signed graph satisfying g ij (G, σ) ≥ g ij (H, π), and such that (G, σ) does not admit any homomorphism to (H, π) while each of its subgraphs does. Extending the notion of excess of k-critical graphs, a natural question is then to give a lower bound on the number of edges of an (H, π)-critical graph. In particular, considering Theorem 6.2 of [START_REF] Naserasr | Homomorphisms of signed graphs[END_REF], the case when (H, π) is a complete bipartite graph with the set of negatives edges being a perfect matching is of special interest.

On the other hand, when (H, π) is a signed projective cube, as discussed in [START_REF] Naserasr | Homomorphisms of planar signed graphs to signed projective cubes[END_REF], the condition of planarity in place of the maximum average degree condition is conjectured to be a sufficient condition. This conjecture directly generalizes the four-color theorem and is in connection with the study of various notions of coloring of planar graphs as discussed in [START_REF] Naserasr | Mapping planar graphs into projective cubes[END_REF].

  admits a homomorphism to (H, π)? For example, for c 10 = c 11 = 10 = 11 = ∞, c 01 = 01 = 3, it is a restatement of the four color theorem, which gives that the signed graph (K 4 , ∅) works. Similarly, if we take c 10 = c 11 = 10 = 11 = ∞, c 01 = 5 and 01 = 3, it is a restatement of Grötzsch's theorem, which gives that the signed graph (K 3 , ∅) works. Furthermore, the Jaeger-Zhang conjecture can be restated to the claim that if c 10 = c 11 = 10 = 11 = ∞, c 01 = 4k + 1 and 01 = 2k + 1, then (C 2k+1 , ∅) is the answer.

Figure 2 :

 2 Figure 2: A subdivision of K 4 .

Figure 4 :

 4 Figure 4: The signed graph (K 4 , {e}).

Figure 5 : 3 Figure 6 :

 536 Figure 5: The colors of x and y forbid at most one pair of colors for v.

Figure 8 :

 8 Figure 8: The two possible forms of the reducible configuration 5, Case 1.

Figure 9 :

 9 Figure 9: The reducible configuration 5, Case 2.

Figure 10 :

 10 Figure 10: The reducible configuration 5, Case 3.

Figure 11 :

 11 Figure 11: The reducible configuration 5, Case 4.

  u

Figure 12 :

 12 Figure 12: The signed graph W 2,2

Acknowledgement. This work is supported by the French ANR project HOSIGRA (ANR-17-CE40-0022). We would like to thank Zhouningxin Wang and Rongxing Xu for helpful discussions. In particular, an error in an earlier version of this paper was discovered during these discussions and is now corrected.

Proof. Assume to the contrary that G contains a 3 3 -vertex u, i.e., a vertex of degree 3 which is adjacent to three 2-vertices (see Figure 6). Then the subgraph of (G, σ) obtained by deleting the set of vertices {u, v 1 , v 2 , v 3 } admits a homomorphism φ to (K 4 , {e}). By Observation 22, each of v 1 , v 2 and v 3 forbids one pair of colors for u, so that at least one pair is still available for extending φ to a homomorphism of (G, σ) to (K 4 , {e}).

Lemma 27 (Reducible configuration 4). If every proper subgraph of (G, σ) maps to (K 4 , {e}), but (G, σ) itself does not, then G has no pair of adjacent 3 2 -vertices.

Proof. Assume to the contrary that u and v are adjacent 3 2 -vertices in G, and let u 1 , u 2 and v 1 , v 2 be the two neighbors of u and v, respectively. Depending on the number of common neighbors of u and v, we have three cases to consider (see Figure 7).

In this case, G consists of two triangles sharing an edge. If the two triangles have the same sign, then the core of the signed graph (G, σ) is a triangle. Regardless of the sign of this triangle, it is a subgraph of (K 4 , {e}) and thus (G, σ) maps to (K 4 , {e}). If the two triangles have different signs, then the signed graph (G, σ) is isomorphic to the signed graph obtained from (K 4 , {e}) by removing the edges 12, and, therefore, maps to (K 4 , {e}).

Let φ be a homomorphism of the subgraph of (G, σ) obtained by deleting the set of vertices {u, v, u 1 , u 2 , v 2 } to (K 4 , {e}). By Observation 22, u 2 forbids one pair of colors for u, and v 2 forbids one pair of colors for v. Let us denote by L(u) and L(v) the sets of six colors available for u and v, respectively. Considering only the edge uv, we know by Observation 21 that for every choice of φ(u), we have three choices for φ(v).

We claim that for at least one choice of φ(u), say c ∈ L(u), the corresponding three choices for φ(v) belong to L(v). Note that since L(u) contains three pairs of colors, we have either C 1 , C 2 ⊆ L(u) or -C 1 , -C 2 ⊆ L(u). Assume the former case occurs, the latter case being similar. By Observation 21, if for some choice φ(u) = c ∈ C 1