A signed graph is a graph together with an assignment of signs to the edges. A closed walk in a signed graph is said to be positive (negative) if it has an even (odd) number of negative edges, counting repetition. Recognizing the signs of closed walks as one of the key structural properties of a signed graph, we define a homomorphism of a signed graph $(G,σ)$ to a signed graph $(H, π)$ to be a mapping of vertices and edges of $G$ to (respectively) vertices and edges of $H$ which preserves incidence, adjacency and the signs of closed walks. In this work we first give a characterization of the sets of closed walks in a graph $G$ that correspond to the set of negative walks in some signed graph on $G$. We also give an easy algorithm for the corresponding decision problem. After verifying the equivalence between this definition and earlier ones, we discuss the relation between homomorphisms of signed graphs and those of 2-edge-colored graphs. Next we provide some basic no-homomorphism lemmas. These lemmas lead to a general method of defining chromatic number which is discussed at length. Finally, we list a few problems that are the driving force behind the study of homomorphisms of signed graphs.

For a graph $G$ and for each vertex $v\in V(G)$, let $\Lambda_G(v) = \{ E_G(v,1), E_G(v,2), \dots , E_G(v,k_v) \}$ be a partition of the edges incident with $v.$ Let $\Lambda_G = \{ \Lambda_G(v) \ | \ v\in V(G) \}.$ We call the pair $(G, \Lambda_G)$ a partitioned graph. Let $k = \max_v k_v$ and let $g,f: V(G) \times \{ 1, \dots ,k \} \rightarrow \mathbb{N}$ and $t,u: V(G) \rightarrow \mathbb{N}$ be functions where, for all vertices $v\in V(G)$, (i) $g(v,i) \le f(v,i) \le d_G(v,i)\ i = 1, \dots ,k_v$, (ii) $u(v) \le t(v) \le d_G(v)$, (iii) $u(v) \le \sum_{i=1}^{k_v}f(v,i)$ and $\sum_{i=1}^{k_v}g(v,i) \le t(v).$ A subgraph $H$ of the partitioned graph is said to be a $(g,f,u,t)$-factor if all vertices $v\in V(G)$ satisfy (a) $g(v,i) \le d_H(v,i) \le f(v,i),\ i = 1, \dots ,k_v$ and (b) $u(v) \le d_H(v) \le t(v)$, where $d_H(v,i)= |E(H) \cap E_G(v,i)|.$ In this paper, we shall show via a reduction to a matching problem, that there is a good algorithm for determining whether a partitioned graph has a $(g,f,u,t)$-factor. Second, we shall also prove a theorem which characterizes the existence of $(0,f,t,u)$-factors in a partitioned graph when $u(v) < f(v,i)$ for all $v$ and $i.$ As a special case, we obtain Lovász's $(g,f)$-factor theorem.

Let H be a graph and $k \geq 3$. A near-unanimity function of arity k is a mapping g from the k-tuples over $V(H)$ to $V(H)$ such that $g(x_1, x_2, \dots, x_k)$ is adjacent to $g(x'_1, x'_2, \dots, x'_k)$ whenever $x_i x'_i \in E(H)$ for each $i = 1, 2, \dots, k$, and $g(x_1, x_2, \dots, x_k) = a$ whenever at least $k-1$ of the $x_i$'s equal a. Feder and Vardi proved that, if a graph H admits a near-unanimity function, then the homomorphism extension (or retraction) problem for H is polynomial time solvable. We focus on near-unanimity functions on reflexive graphs. The best understood are reflexive chordal graphs H: they always admit a near-unanimity function. We bound the arity of these functions in several ways related to the size of the largest clique and the leafage of H, and we show that these bounds are tight. In particular, it will follow that the arity is bounded by $n -\sqrt{n}+1$, where $n = |V(H)|$. We investigate substructures forbidden for reflexive graphs that admit a near-unanimity function. It will follow, for instance, that no reflexive cycle of length at least four admits a near-unanimity function of any arity. However, we exhibit nonchordal graphs which do admit near-unanimity functions. Finally, we characterize graphs which admit a conservative near-unanimity function. This characterization has been predicted by the results of Feder, Hell, and Huang. Specifically, those results imply that, if P $\neq$ NP, the graphs with conservative near-unanimity functions are precisely the so-called bi-arc graphs. We give a proof of this statement without assuming P $\neq$ NP.