% EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} % Please remove all commands that change parameters such as % margins or page sizes. % Packages amssymb and amsthm are already loaded. % We recommend these AMS packages: \usepackage{amsmath,amssymb} % We recommend the graphicx package for importing figures: \usepackage{graphicx} % Use this command to create hyperlinks (optional and recommended): \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} % Theorem-like environments that are declared in the style file are: % theorem, lemma, corollary, proposition, fact, observation, claim, % definition, example, conjecture, open, problem, question, remark, note %%%%%%%%%%%%%METADATA%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Give the submission and acceptance dates in the format shown. % The editors will insert the publication date in the third argument. \dateline{Dec 6, 2014}{May 16, 2018}{TBD} % Give one or more subject codes separated by commas. % Codes are available from http://www.ams.org/mathscinet/freeTools.html \MSC{05C88, 05C89} % Uncomment exactly one of the following copyright statements. Alternatively, % you can write your own copyright statement subject to the approval of the journal. % See https://creativecommons.org/licenses/ for a full explanation of the % Creative Commons licenses. % % We strongly recommend CC BY-ND or CC BY. Both these licenses allow others % to freely distribute your work while giving credit to you. The difference between % them is that CC BY-ND only allows distribution unchanged and in whole, while % CC BY also allows remixing, tweaking and building upon your work. % % One author: %\Copyright{The author.} %\Copyright{The author. Released under the CC BY license (International 4.0).} %\Copyright{The author. Released under the CC BY-ND license (International 4.0).} % More than one author: %\Copyright{The authors.} %\Copyright{The authors. Released under the CC BY license (International 4.0).} \Copyright{ The authors. Released under the CC BY-ND license (International 4.0).} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % If needed, include a line break (\\) at an appropriate place in the title. \title{Flows in signed graphs with two negative edges} % Input author, affiliation, address and support information as follows; % The address should include the country, but does not have to include % the street address. Give at least one email address. \author{Edita Rollov\'a\thanks{Supported by the project LO1506 of the Czech Ministry of Education, Youth and Sports and by the projects GA14-19503S and GA17-04611S of the Czech Science Foundation.}\\ \small European Centre of Excellence, New Technologies for the Information Society\\[-0.8ex] \small Faculty of Applied Sciences, University of West Bohemia\\[-0.8ex] \small Plze\v n, Czech Republic\\ \small\tt rollova@ntis.zcu.cz\\ \and Michael Schubert \qquad Eckhard Steffen\\ \small Paderborn Center for Advanced Studies and Institute for Mathematics\\[-0.8ex] \small Paderborn University\\[-0.8ex] \small Paderborn, Germany\\ \small\tt \{mischub,es\}@upb.de} \begin{document} \maketitle % E-JC papers must include an abstract. The abstract should consist of a % succinct statement of background followed by a listing of the % principal new results that are to be found in the paper. The abstract % should be informative, clear, and as complete as possible. Phrases % like "we investigate..." or "we study..." should be kept to a minimum % in favor of "we prove that..." or "we show that...". Do not % include equation numbers, unexpanded citations (such as "[23]"), or % any other references to things in the paper that are not defined in % the abstract. The abstract may be distributed without the rest of the % paper so it must be entirely self-contained. Try to include all words % and phrases that someone might search for when looking for your paper. \begin{abstract} The presented paper studies the flow number $F(G,\sigma)$ of flow-admissible signed graphs $(G,\sigma)$ with two negative edges. We restrict our study to cubic graphs, because for each non-cubic signed graph $(G,\sigma)$ there is a set of cubic graphs obtained from $(G,\sigma)$ such that the flow number of $(G,\sigma)$ does not exceed the flow number of any of the cubic graphs. We prove that $F(G,\sigma) \leq 6$ if $(G,\sigma)$ contains a bridge, and $F(G,\sigma) \leq 7$ in general. We prove better bounds, if there is a cubic graph $(H,\sigma_H)$ obtained from $(G,\sigma)$ which satisfies some additional conditions. In particular, if $H$ is bipartite, then $F(G,\sigma) \leq 4$ and the bound is tight. If $H$ is $3$-edge-colorable or critical or if it has a sufficient cyclic edge-connectivity, then $F(G,\sigma) \leq 6$. Furthermore, if Tutte's $5$-Flow Conjecture is true, then $(G,\sigma)$ admits a nowhere-zero $6$-flow endowed with some strong properties. \end{abstract} \section{Introduction} In 1954 Tutte stated a conjecture that every bridgeless graph admits a nowhere-zero $5$-flow (\textit{5-flow conjecture}, see \cite{Tutte_1954}). Naturally, the concept of nowhere-zero flows has been extended in several ways. In this paper we study one generalization of them -- nowhere-zero integer flows on signed graphs. Signed graphs are graphs where each edge is either positive or negative. It was conjectured by Bouchet \cite{Bouchet_1983} that signed graphs that admit a nowhere-zero flow have a nowhere-zero $6$-flow. Recently, it was announced by DeVos \cite{DeVos} that such signed graphs admit a nowhere-zero $12$-flow, which is the best current general approach to Bouchet's conjecture. Bouchet's conjecture has been confirmed for particular classes of graphs \cite{MS,MR,SS} and also for signed graphs with restricted edge-connectivity (for example \cite{Raspaud_Zhu_2011}). By Seymour \cite{Sey} it is also true for signed graphs with all edges positive, because they correspond to the unsigned case. For more details on flows on signed graphs, consult \cite{survey}. In this paper we study signed graphs with two negative edges. It is the minimum number of negative edges for which Bouchet's conjecture is open, because signed graphs with one negative edge are not flow-admissible. This class of signed graphs is further interesting for its connection with Tutte's $5$-flow conjecture. Suppose there exists $k$ such that every signed graph with $k$ negative edges admits a nowhere-zero $5$-flow. Take any bridgeless graph $G$ and identify a vertex of all-positive $G$ with a vertex of a flow-admissible signed graph with $k$ negative edges. The resulting signed graph is flow-admissible with $k$ negative edges. If it admits a nowhere-zero $5$-flow, then $G$ {admits it} as well. Therefore the following holds. \begin{observation} If there exists $k$ such that every flow-admissible signed graph with $k$ negative edges admits a nowhere-zero $5$-flow, then Tutte's conjecture is true. \end{observation} Since for every $k\geq 3$ there is a flow-admissible signed graph with $k$ negative edges which does not admit a nowhere-zero $5$-flow (see \cite{SS}), but there is no such example known for $k=2$, the class of signed graphs with two negative edges is of a great importance. In the opposite direction we will prove that Tutte's conjecture implies Bouchet's conjecture for signed graphs with two negative edges. In the next section we introduce necessary notions and provide a couple of well-known results on flows. In Section 3 we show how to deal with small edge-cuts, and finally, in Sections 4-6 we prove results on flows for signed graphs with two negative edges. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Preliminaries} Graphs in this paper are allowed to have multiple edges and loops. \textit{A signed graph} $(G,\sigma)$ consists of a graph $G$ and a function $\sigma:\ E(G) \to \{-1,1\}$. The function $\sigma$ is called \textit{a signature}. The set of edges with negative signature is denoted by $N_\sigma$. It is called \textit{the set of negative edges}, while $E(G) - N_{\sigma}$ is called \textit{the set of positive edges}. If all edges of $(G,\sigma)$ are positive, i. e. when $N_\sigma=\emptyset$, then $(G,\sigma)$ will be denoted by $(G,\texttt{1})$ and will be called an \textit{all-positive signed graph}. Let $e \in E(G)$ be an edge, which is incident with vertices $u$ and $v$. We divide $e$ into two half-edges $h^{e}_{u}$ and $h^{e}_{v}$, one incident with $u$ and one incident with $v$. The set of the half-edges of $G$ is denoted by $H(G)$. For each half-edge $h \in H(G)$, the corresponding edge in $E(G)$ is denoted by $e_h$. For a vertex $v$, $H(v)$ denotes the set of half-edges incident with $v$. An \textit{orientation} of $(G,\sigma)$ is a function $\tau : H(G) \rightarrow \{ \pm 1 \}$ such that $\tau(h^{e}_{u})\tau(h^{e}_{v}) = - \sigma(e)$, for each edge $e=uv$. The function $\tau$ can be interpreted as an assignment of a direction to each edge in the following way. A positive edge can be directed like \includegraphics[scale=0.1]{edge_1.eps} or like \includegraphics[scale=0.1]{edge_2.eps}. A negative edge can be directed like \includegraphics[scale=0.1]{edge_3.eps} (so-called \textit{extroverted edge}) or like \includegraphics[scale=0.1]{edge_4.eps} (so-called \textit{introverted edge}). {In what follows we will often start with a particular orientation, and then redirect some half-edges (change their direction to the opposite one) in order to obtain a new orientation. Note that if we redirect one half-edge of an oriented positive edge, we obtain an oriented negative edge. If we redirect both half-edges of an oriented positive edge, we obtain a positive edge with the opposite orientation. This can be viewed as redirection of a positive edge. It will be used when we study unsigned or all-positive signed graphs.} Half-edges incident with $v$ that are oriented towards $v$ (away from $v$, respectively) will be called \textit{incoming half-edges} (\textit{outgoing half-edges}, respectively) and will be denoted by $\delta^-(v)$ ($\delta^+(v)$, respectively). In case of positive edges we also use $e \in \delta^+(v)$ ($e \in \delta^-(v)$) if $e$ is incident with $v$, and if there is no danger of confusion. Let $(G,\sigma)$ be a signed graph. \textit{A switching at $v$} defines a signed graph $(G,\sigma')$ with $\sigma'(e) = -\sigma(e)$ if $e$ is incident with $v$, and $\sigma'(e) = \sigma(e)$ otherwise. We say that signed graphs $(G,\sigma)$ and $(G,\sigma^*)$ are \textit{equivalent} if they can be obtained from each other by a sequence of switchings. We also say that $\sigma$ and $\sigma^*$ are \textit{equivalent signatures} of $G$. If we consider a signed graph with an orientation $\tau$, then switching at $v$ is a change of the orientations of the half-edges that are incident with $v$, {i. e. on half-edges $h_v^{e}$ for every $e$ incident with $v$}. If $\tau^*$ is the resulting orientation, then we say that $\tau$ and $\tau^*$ are \textit{equivalent orientations}. Let $A$ be an abelian group. An \emph{$A$-flow} $(\tau,\phi)$ on $(G,\sigma)$ consists of an orientation $\tau$ and an assignment $\phi : E(G) \rightarrow {A}$ satisfying \textit{Kirchhoff's law}: {for every vertex $v$ the sum of values on incoming half-edges equals the sum of values on outgoing half-edges.} If $\phi(e) \not = 0$ for every edge $e$, then we say that the $A$-flow is \textit{nowhere-zero}. Let $k$ be a positive integer. A nowhere-zero $\mathbb{Z}$-flow such that $ -k< \phi(e) 0$ for every $e \in E(G)$, then for any two vertices $u$,$v$ of $G$ there exists a directed $u$-$v$-path. \end{lemma} \begin{observation}\label{obser:opp} Suppose that there exists a nowhere-zero $k$-flow $(\tau,\phi)$ with $\phi(f)=t$ for one direction of $f$. Let $\tau_{opp}$ be the orientation obtained from $\tau$ by reversing the direction of each edge of $G$. Then $(\tau_{opp},\phi)$ is a nowhere-zero $k$-flow with $\phi(f)=t$ for the other direction of $f$. \end{observation} Flows on signed graphs were introduced by Bouchet~\cite{Bouchet_1983}, who stated the following conjecture. \begin{conjecture} [\cite{Bouchet_1983}] \label{Bouchet_conj} Let $(G,\sigma)$ be a signed graph. If $(G,\sigma)$ is flow-admissible, then $(G,\sigma)$ admits a nowhere-zero $6$-flow. \end{conjecture} The $6$-flow theorem of Seymour~\cite{Sey} proves Bouchet's conjecture for all-positive signed graphs. \begin{theorem} [\cite{Sey}] \label{6_Flow} If $(G,\texttt{1})$ is flow-admissible, then $(G,\texttt{1})$ admits a nowhere-zero $6$-flow. \end{theorem} In this paper, we restrict our study to signed cubic graphs, because for each signed non-cubic graph $(G,\sigma)$ there is a set ${\cal G}(G,\sigma)$ of signed cubic graphs such that $F(G, \sigma) \leq \min \{F(H,\sigma_H) : (H,\sigma_H) \in {\cal G}(G,\sigma)\}$. The set ${\cal G}(G,\sigma)$ is obtained from $(G,\sigma)$ by suppressing the vertices of degree 2 and by blowing vertices of degree higher than 3 into a circuit. More precisely, if $v$ is a vertex of degree $2$ in $(G,\sigma)$ with $u$ and $w$ being its neighbours, then a new signed graph is obtained by deleting $v$ (together with $uv$ and $vw$), and by adding a new edge $uw$ whose sign is $\sigma(uv)\cdot\sigma(vw)$. If $v$ is a vertex of degree $d=\deg(v)\geq 4$ with neighbours $u_1,\ldots,u_d$, then a new signed graph is obtained by deleting $v$ (together with $vu_1,\ldots vu_d$), adding new vertices $v_1,\ldots, v_d$ that induce an all-positive circuit, and adding new edges $v_1u_1,\ldots, v_du_d$ with $\sigma(v_iu_i)=\sigma(vu_i)$ for $i\in\{1,\ldots,d\}$. The distinct members of ${\cal G}(G,\sigma)$ are obtained by repeating the above mentioned methods in distinct order. Sometimes it is useful to apply the methods in such order that an additional property (such as edge-connectivity) is preserved. Note that any member of ${\cal G}(G,\sigma)$ is flow-admissible whenever $(G,\sigma)$ is.\medskip We finish this section by recalling a few standard graph definitions. \textit{A (proper) edge-coloring} of a graph $G$ is an assigment of a color to every edge of $G$ in such a way that any two adjacent edges obtain different colors. We say that $G$ is \textit{$k$-edge-colorable} if there exists an edge-coloring of $G$ that uses at most $k$ colors. The smallest number of colors needed to edge-color $G$ is the \textit{chromatic index of $G$}. By Vizing's theorem the chromatic index of a cubic graph is either 3 or 4. Tutte \cite{Tutte_1949, Tutte_1954} proved that a cubic graph $G$ is $3$-edge-colorable if and only if $G$ admits a nowhere-zero $4$-flow, and that $G$ is bipartite if and only if $G$ admits a nowhere-zero $3$-flow. Bridgeless cubic graphs which do not have a nowhere-zero 4-flow are called \textit{snarks}. We say that a snark $G$ is \textit{critical} if $G-e$ admits a nowhere-zero $4$-flow for every edge $e$. Critical snarks were studied for example in \cite{Kochol_2011, Nedela_Skoviera_1996, Steffen_1998}. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Small edge-cuts} \label{sec:small edge cuts} In Section \ref{sec:6-flows} we will show that Bouchet's conjecture holds for signed graphs with two negative edges that contain bridges. In this section we will deal with $2$-edge-cuts that do not separate negative edges, and refer to them as {non-separating} 2-edge-cuts. An idea to reduce non-separating cuts of size less than 3 appeared first in Bouchet's work (see Proposition 4.2.~in~\cite{Bouchet_1983}). However, his reduction uses contraction of a positive edge, which cannot be used in our paper -- contraction of an edge of a signed graph from a particular class (e.g. bipartite) may result in a signed graph that does not belong to the same class. Here, we introduce a reduction of $2$-edge-cuts (different from the one introduced by Bouchet~\cite{Bouchet_1983}), which will be applied several times in the proofs of our main results. Let $X$ be an edge-cut of $(G,\sigma)$, and let $(W_1,W_2)$ be a partition of $V(G)$ such that $w_1w_2\in X$ if and only if $w_1\in W_1$ and $w_2\in W_2$. Switching at all vertices of $W_1$ results in a signed graph $(G,\sigma')$ such that $\sigma(e)\neq \sigma'(e)$ if and only if $e\in X$. Thus, the following three statements hold. \begin{lemma}\label{lemma:p2edgecut} Let $(G,\sigma)$ be a signed graph and $X \subseteq E(G)$ be an edge-cut of $G$. If $X=N_{\sigma}$, then $F(G,\sigma)= F(G,\texttt{1})$. \end{lemma} \begin{lemma}\label{lemma:noflow} Let $(G,\sigma)$ be a signed graph such that all negative edges $N_{\sigma}$ belong to an $(|N_{\sigma}|+1)$-edge-cut. Then $(G,\sigma)$ is not flow-admissible. \end{lemma} \begin{corollary}\label{cor:3edgecut} Let $(G,\sigma)$ be a signed graph such that $|N_{\sigma}|=2$. If $(G,\sigma)$ is flow-admissible, then the two negative edges of $(G,\sigma)$ do not belong to any $3$-edge-cut. \end{corollary} \subsection*{2-edge-cuts} When we study (non-separating) $2$-edge-cuts, we always assume that the $2$-edge-cut is a matching. Let $X=\{e_1,e_2\}$ be a $2$-edge-cut of $(G,\sigma)$ such that $(G-X,\sigma|_{G-X})$ has precisely two components $G_1^-$, $G_2^-$, where $G_2^-$ is all-positive. Then $X$ is called a \textit{non-separating 2-edge-cut}. Let $e_1 = u_1u_2$ and $e_2 = v_1v_2$, and $u_i, v_i \in V(G_i^-)$. If $X=N_{\sigma}$, then $F(G,\sigma)\leq 6$ by Lemma~\ref{lemma:p2edgecut} and Theorem~\ref{6_Flow}. For this reason we are interested in non-separating $2$-edge-cuts with at least one positive edge, say $e_2$. A \textit{$2$-edge-cut reduction of $(G,\sigma)$} with respect to the edge-cut $X$ is a disjoint union of two signed graphs $(G_1,\sigma_{1})$ and $(G_2,\sigma_{2})$, where $(G_i,\sigma_i)$ is obtained from $G_i^-$ by adding an edge $f_i$ between $u_i$ and $v_i$ and setting $\sigma_i(f_i) = \sigma(e_i)$. Note that $(G_2,\sigma_2)$ is all-positive. We say that $(G,\sigma)$ is \textit{$2$-edge-cut reducible} and that $(G_1,\sigma_{1})$ and $(G_2,\texttt{1})$ are the \textit{resulting graphs} of the $2$-edge-cut reduction of $(G,\sigma)$ (with respect to the (non-separating) $2$-edge-cut $X$). In what follows, when we refer to a $2$-edge-cut reduction of a signed graph, then we always use the same notation as in the above definition. \begin{lemma}\label{obser:2red} Let $(G,\sigma)$ be a flow-admissible signed graph. If $(G,\sigma)$ is $2$-edge-cut reducible with respect to a $2$-edge-cut $X$, then the two resulting graphs are flow-admissible. \end{lemma} \begin{proof} Let $(G_1,\sigma_{1})$ and $(G_2,\texttt{1})$ be the resulting signed graphs of the $2$-edge-cut reduction of $(G,\sigma)$ with respect to $X=\{e_1,e_2\}$. We are going to prove that each edge of the resulting graphs belongs to a signed circuit. Suppose first that $e\in E(G)\cap E(G_i)$, for $i\in\{1,2\}$. Since $(G,\sigma)$ is flow-admissible, there exists a signed circuit $C$ of $(G,\sigma)$ containing $e$ according to Lemma~\ref{flow-admissible}. If $E(C)\subseteq E(G_i)$, then we are done. Otherwise, $C$ contains at least one of $\{e_1,e_2\}$. Since $(G_2,\texttt{1})$ is all-positive, $C$ must contain both of $\{e_1,e_2\}$. Let $P$ be a path of $C$ that does not belong to $G_i$ (note that $P$ is a path since edges of $X$ are independent, and that $\{e_1,e_2\}\subseteq E(P)$). Then $C-P\cup \{f_i\}$ is a signed circuit of $G_i$ containing $e$. Note that any such circuit also contains an edge $f_i\in E(G_i)-E(G)$, so we are done if there exists a signed circuit $C$ of $(G,\sigma)$ such that $E(C)\nsubseteq E(G_i)$. But if there is no such circuit of $(G,\sigma)$, then $e_i$ is not contained in any signed circuit, which is a contradiction with flow-admissibility of $(G,\sigma)$. \end{proof} \begin{lemma}\label{lemma:n2edgecut} Let $(G_1,\sigma_{1})$ and $(G_2,\sigma_{2})$ be the resulting graphs of the $2$-edge-cut reduction of $(G,\sigma)$ with respect to a $2$-edge-cut $\{e_1, e_2\}$. Let $k$ be a positive integer, and for $i \in \{1,2\}$, let $(G_i,\sigma_{i})$ admit a nowhere-zero $k$-flow $(\tau_i,\phi_i)$. If $\phi_1(f_1)=\phi_2(f_2)$, then $F(G,\sigma)\leq k$. \end{lemma} \begin{proof} Let $\tau$ be an orientation of the edges of $(G,\sigma)$ such that $\tau(e)=\tau_i(e)$ for every edge $e\in E(G_i)\cap E(G)$. By Observation~\ref{obser:opp}, we may assume that $e_1 \in \delta^+(u_2)$ and $e_2\in \delta^+(v_1)$. Now $(\tau,\phi)$ with $\phi(e)=\phi_i(e)$ for every $e\in E(G_i)\cap E(G)$ and $\phi(e_1)=\phi(e_2)=\phi_1(f_1)$ is a nowhere-zero $k$-flow on $(G,\sigma)$. \end{proof} For a signed graph $(G,\sigma)$ with two negative edges we say that an all-positive $2$-edge-cut $X$ \emph{separates the negative edges} if the negative edges belong to different components of $G-X$. We note that we will not use an equivalent of a $2$-edge-cut reduction for $2$-edge-cuts that separate negative edges, because the resulting signed graphs may not be flow-admissible. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Nowhere-zero 4-flows} \label{sec:4-flows} The following lemma is due to Sch\"onberger \cite{Sch}. \begin{lemma}[\cite{Sch}]\label{lemma:matchingwithe} If $G$ is a bridgeless cubic graph and $e$ is an edge of $G$, then $G$ has a $1$-factor that contains $e$. \end{lemma} \begin{lemma}\label{lemma:1factor} Let $G$ be a cubic bipartite graph, and let $e,f \in E(G)$. If any $3$-edge-cut contains at most one edge of $\{e,f\}$, then there exists a $1$-factor of $G$ that contains both $e$ and $f$. \end{lemma} \begin{proof} Let $U$ and $V$ be the partite sets of $G$. Let $e=u_1v_1$ and $f=u_2v_2$ be two edges of $G$ such that $u_1,u_2\in U$ and $v_1,v_2\in V$. If $e$ and $f$ are adjacent, they belong to a (trivial) $3$-edge-cut of $G$ and there is nothing to prove. Hence, $e$ and $f$ are non-adjacent. If $e$ and $f$ form a $2$-edge-cut, then they must belong to the same color class of a $3$-edge-coloring of $G$ and hence, there is a $1$-factor that contains $e$ and $f$. In what follows, we assume that $\{e,f\}$ is not a $2$-edge-cut. Let $G'$ be the graph that is constructed from $G - \{e,f\}$ by adding new edges $e'=u_1u_2$ and $f'=v_1v_2$. It follows that $G'$ is cubic and bridgeless (since $e$ and $f$ do not belong to any $3$-edge-cut of $G$). Thus, by Lemma~\ref{lemma:matchingwithe}, there exists a $1$-factor $F'$ of $G'$ containing $e'$. We claim that $F'$ contains $f'$. Suppose to the contrary that $f'\notin F'$. Then there exist $u_1'$ and $u_2'$ from $U$ such that $v_1u_1'$ and $v_2u_2'$ are in $F'$. The graph $G'-\{u_1, u_1', u_2, u_2', v_1, v_2\}$ is bipartite with partite sets of cardinality $|U|-4$ and $|V|-2=|U|-2$. Note that such a graph does not have any $1$-factor, which is a contradiction with the existence of $F'$. Thus, $f'$ must belong to $F'$. In that case $F=F'\cup\{e,f\}-\{e',f'\}$ is a $1$-factor of $G$ that contains $e$ and $f$. \end{proof} \begin{lemma}\label{prop:1factorimplies4flow} Let $(G,\sigma)$ be a signed cubic graph with $N_{\sigma}=\{n_1,n_2\}$. If $G$ has a $3$-edge-coloring such that $n_1$ and $n_2$ belong to the same color class, then $(G,\sigma)$ admits a nowhere-zero $4$-flow $(\tau,\phi)$ such that $\phi(n_1)=\phi(n_2)=2$. \end{lemma} \begin{proof} Let $c:\ E(G) \to \{c_1,c_2,c_3\}$ be a $3$-edge-coloring such that $c(n_1)=c(n_2)=c_1$. It is easy to see that $(G,\texttt{1})$ has a nowhere-zero $4$-flow $(\tau,\phi)$ such that $\phi(e) > 0$ for every $e \in E(G)$ and $\phi(f) = 2$ if $f \in c^{-1}(c_1)$. {Let $n_1 = u_1u_2$ and $n_2 = v_1v_2$, and let, without loss of generality,} $n_1 \in \delta^+(u_1)$ and $n_2 \in \delta^+(v_1)$. If $N_{\sigma}$ is a $2$-edge-cut, then the statement follows from Lemma \ref{lemma:p2edgecut}. It remains to consider the case when $N_{\sigma}$ is not a $2$-edge-cut. Since $c(n_1)=c(n_2)$, the edges $n_1$ and $n_2$ do not belong to a $3$-edge-cut by parity reasons. Hence, every edge-cut that contains $n_1$ and $n_2$ has at least $4$ edges. Note, that by Lemma~\ref{lemma:directeduvpath}, there is a directed $v_2$-$u_1$-path $P$ that contains neither $n_1$ nor $n_2$. Let $\tau'$ be the orientation of $(G,\sigma)$ which is obtained from $\tau$ by reversing the orientation of the half-edges $h_{u_1}^{n_1}$ and $h_{v_2}^{n_2}$ and of the edges of $P$. Let $\phi'(x) = 4- \phi(x)$ if $x \in E(P)$, and $\phi'(x) = \phi(x)$ otherwise. It is easy to check that $(\tau',\phi')$ is the required nowhere-zero $4$-flow on $(G,\sigma)$. \end{proof} \begin{theorem}\label{thm:cubbip} Let $(G,\sigma)$ be a flow-admissible signed cubic graph with $|N_{\sigma}|=2$. If $G$ is bipartite, then $F(G,\sigma)\leq 4$. \end{theorem} \begin{proof} Let $N_{\sigma}=\{n_1, n_2\}$. Since $(G,\sigma)$ is flow-admissible, $n_1$ and $n_2$ do not belong to any $3$-edge-cut by Corollary~\ref{cor:3edgecut}. Thus, by Lemma~\ref{lemma:1factor}, $G$ has a $1$-factor containing $n_1$ and $n_2$. By Lemma~\ref{prop:1factorimplies4flow}, $F(G,\sigma)\leq 4$. \end{proof} The bound given in Theorem~\ref{thm:cubbip} is tight. It is achieved for example on $(K_{3,3},\sigma)$, where the two negative edges form a matching (see \cite{MR}). It is not possible to extend the result of Theorem~\ref{thm:cubbip} to cubic bipartite graphs with any number of negative edges. For example, a circuit of length $6$, where every second edge is doubled and one of the parallel edges is negative for every pair of parallel edges while all the other edges are positive, has flow number $6$ (see \cite{SS}). We would like to note that the choice of the flow value on negative edges is important. The signed graph in Figure~\ref{fig} (where the depicted values represent the signature) is an example of a signed graph that does not admit a nowhere-zero $4$-flow that assigns 1 to negative edges even though it admits a nowhere-zero $4$-flow according to Theorem~\ref{thm:cubbip}. For the proof, suppose to the contrary that $(G,\sigma)$ admits a nowhere-zero $4$-flow that assigns 1 to negative edges. Let all positive edges of $(G,\sigma)$ be oriented from left to right and from top to bottom with respect to the embedding depicted in Figure~\ref{fig}. Furthermore, let the top negative edge be extroverted, and let the bottom one be introverted, both carrying the flow value 1. If the horizontal positive edges carry the flow values $a$, $(-a-b)$ and $b$ (assigned from top to bottom), then due to the vertical edges, we have the following constraints on values $a$ and $b$: $a\neq \pm 1$ and $b\neq \pm 1$ (vertical edges would carry value 0), $a\neq \pm 3$ and $b\neq \pm 3$ (vertical edges would carry value 4 or -4). Thus, $|a|=|b|=2$, resulting in the flow value 0 or $\pm 4$ on the middle horizontal positive edge, which carries the flow value $(-a-b)$ by Kirchhoff's law. This is a contradiction. \begin{figure}[h] \begin{center} \includegraphics[width=6cm]{fig.eps} \caption{{A signed graph for which the choice of the flow value on negative edges is important.}}\label{fig} \end{center} \end{figure} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Nowhere-zero 6-flows} \label{sec:6-flows} In this section we prove that Bouchet's conjecture is true for signed graphs with two negative edges where the underlying graph has additional properties. Our first result is on signed graphs with bridges, for which we need some lemmas. Tutte~\cite{Tutte_1954} proved that a graph has a nowhere-zero $k$-flow if and only if it has a nowhere-zero $\mathbb{Z}_k$-flow. This is not true for general signed graphs, but in our paper we will apply the following theorem, which is a straightforward corollary of Theorem 3.2 in~\cite{JLPT}. Note that the following theorem as well as the subsequent lemma deal with unsigned graphs, but they can be applied to all-positive signed graphs too. \begin{theorem}[\cite{JLPT}]\label{JLPT} Let $G$ be a $3$-edge-connected graph, and let $v\in V(G)$ be a vertex of degree~3 incident with edges $e_1,e_2,e_3$. Suppose that $\tau$ is an orientation of $G$ such that $\delta^+(v)=\{e_1,e_2\}$, and $\delta^-(v)=\{e_3\}$. If $a_1,a_2,a_3\in \mathbb{Z}_6 - \{0\}$ are such that $a_1+a_2=a_3$, then $G$ admits a nowhere-zero $\mathbb{Z}_6$-flow $(\tau,\phi)$ such that $\phi(e_i)=a_i$, for $i\in\{1,2,3\}$. \end{theorem} Let $\tau$ be an orientation of a graph $G$ and $\phi:\ E(G) \to \mathbb{Z}_k$ ($k \geq 2$) be a flow on $G$. We now calculate in $\mathbb{Z}$. Let $\zeta(v) = \sum_{e \in \delta^+(v)}\phi(e) - \sum_{e \in \delta^-(v)}\phi(e)$ be the (integer) \emph{outflow} of $v$ and let $\Theta(G,(\tau,\phi)) = \sum_{v \in V(G)}|\zeta(v)|$. This notation is used in proof of the following lemma, which is an extension of a classical result by Tutte~\cite{Tutte_1954}. \begin{lemma}\label{magictrick} Let $G$ be a graph, and let $w$ be a vertex of $G$ of degree 3 incident with $e_1,e_2,e_3 \in E(G)$. Suppose that $G$ admits a nowhere-zero $\mathbb{Z}_k$-flow $(\tau,\phi)$ such that \begin{enumerate} \item[(i)] $\delta^+(w)=\{e_1,e_2\}$ and $\delta^-(w)=\{e_3\}$, \item[(ii)] $\phi(e_1)= 1$, \item[(iii)] $\phi(e_2) = a$, for some $a \in \{1,\dots,k-2\}$, and \item[(iv)] $\phi(e_3) = 1+a$. \end{enumerate} Then $G$ admits a nowhere-zero $k$-flow $(\tau,\psi)$ such that $\psi(e_i)= \phi(e_i)$, for $i\in\{1,2,3\}$. \end{lemma} \begin{proof} Let $G$, $w$, $e_1,e_2,e_3$, and $(\tau,\phi)$ be as described in the lemma. Since $(\tau,\phi)$ is a nowhere-zero $\mathbb{Z}_k$-flow, $\zeta(v)$ is a multiple of $k$ (including 0) for every $v \in V(G)$. Furthermore, $\sum_{v \in V(G)}\zeta(v) = 0$, because for every edge $e$ of $G$, $\phi(e)$ contributes to the sum twice (once for each end-vertex of $e$), but with different signs. If $\Theta(G,(\tau,\phi)) = \sum_{v \in V(G)}|\zeta(v)| = 0$, then $(\tau,\phi)$ is a nowhere-zero $k$-flow, and we are done. Thus, we may assume that $\Theta(G,(\tau,\phi)) \not = 0$. This and Kirchhoff's law extended to a set of vertices imply that there exist vertices $x, y$ connected by a directed path $P$ such that $\zeta(x) > 0$ and $\zeta(y) < 0$. Let $\tau'$ be the orientation of $G$ obtained from $\tau$ by reversing the direction of the edges of $P$. Let $\phi'(e) = k - \phi(e)$ if $e \in E(P)$, and let $\phi'(e) = \phi(e)$ otherwise. Then $(\tau',\phi')$ is a nowhere-zero $\mathbb{Z}_k$-flow on $G$. Furthermore, $\Theta(G,(\tau',\phi')) < \Theta(G,(\tau,\phi))$. Repeating this procedure eventually gives a nowhere-zero $k$-flow $(\tau_1,\phi_1)$ on $G$, and we may assume that $\phi_1(e) > 0$ for all $e \in E(G)$. From the procedure follows that at least one of $e_1,e_2$ belongs to $\delta^+(w)$. If $\delta^+(w)=\{e_1,e_2\}$, then $(\tau_2,\phi_2):=(\tau_1,\phi_1)$ is a nowhere-zero $k$-flow on $G$ which coincides with $(\tau,\phi)$ on $\{e_1,e_2,e_3\}$. It remains to consider that exactly one of $e_1,e_2$, say $e_j$, belongs to $\delta^-(w)$. Note that in this case, $e_3\in \delta^+(w)$, $\phi_1(e_j)=k-\phi(e_j)$, and $\phi_1(e_3)=k-\phi(e_3)$. Now, $e_3$ is contained in a directed circuit $C$ which also contains $e_j$. Change the direction of the edges of $C$ to obtain $\tau_2$ and for $e \in E(C)$ replace $\phi_1(e)$ by $k-\phi_1(e)$ to obtain $\phi_2$. Then $(\tau_2,\phi_2)$ is a nowhere-zero $k$-flow on $G$ which coincides with $(\tau,\phi)$ on $\{e_1,e_2,e_3\}$. As the last step we need to modify edges for which $\tau_2\neq \tau$. Let $\psi(e)=-\phi_2(e)$ (in $\mathbb{Z}$) for $e \in E(G)$ with $\tau_2(e)\neq \tau(e)$, and let $\psi(e)=\phi_2(e)$ otherwise. Then $(\tau,\psi)$ is the required nowhere-zero $k$-flow of $G$. \end{proof} \begin{corollary} \label{6_Flow_1} Let $G$ be a cubic graph, $f \in E(G)$ and $t \in \{1,\dots,5\}$. If $G$ is bridgeless, then $(G,\texttt{1})$ has a nowhere-zero $6$-flow $(\tau,\phi)$ such that $\phi(f)=t$, for each possible direction of $f$, and $\phi(e)> 0$, for each $e \in E(G)$. \end{corollary} \begin{proof} By Theorem~\ref{6_Flow}, $(G,\texttt{1})$ admits a nowhere-zero $6$-flow (or, equivalently, a nowhere-zero $\mathbb{Z}_6$-flow). We need to show that we can choose the flow value on $f$. By Observation~\ref{obser:opp}, we only need to prove the statement for different values of $t$ irrespective of the direction of $f$. Suppose the contrary, and let $G$ be a counterexample with minimum number of edges. If $G$ is $3$-edge-connected, we obtain a contradiction with Theorem~\ref{JLPT} and Lemma~\ref{magictrick}. Thus, we may assume that $G$ has a $2$-edge-cut $X=\{e_1,e_2\}$. Viewing $G$ as $(G,\texttt{1})$, we may use the $2$-edge-cut reduction with respect to $X$ defined in Section~\ref{sec:small edge cuts}. By Lemma~\ref{obser:2red}, the resulting graphs $G_1$ and $G_2$ are flow-admissible. Moreover, they are both smaller than $G$, and therefore they admit a nowhere-zero $6$-flow such that we can choose the flow value on one edge. If $f \notin X$, then we first choose the requisite flow for $G_i$ which contains $f$, and then we choose the flow for $G_{3-i}$ in such a way that the flow values on $f_1$ and $f_2$ coincide (recall that $f_i\in E(G_i)-E(G)$, for $i\in\{1,2\}$). If $f\in X$, then we choose the flow on $G_i$ in such a way that $f_i$ receives the flow value $t$, for each $i\in\{1,2\}$. By Lemma~\ref{lemma:n2edgecut}, $G$ has the required nowhere-zero $6$-flow, which is a contradiction. \end{proof} \begin{theorem}\label{thm:bridges} Let $(G,\sigma)$ be a flow-admissible signed cubic graph with two negative edges. If $(G,\sigma)$ contains a bridge, then $(G,\sigma)$ admits a nowhere-zero $6$-flow $(\tau,\phi)$ with the flow value $1$ on the negative edges. \end{theorem} \begin{proof} Let $n_1$ and $n_2$ be the two negative edges of $(G,\sigma)$. Since $(G,\sigma)$ is flow-admissible, it follows that all bridges are positive edges according to Lemma~\ref{flow-admissible}. We will prove the statement by induction on the order of the graph. If $|V(G)|=2$, then $(G,\sigma)$ is the graph with one positive edge and a negative loop on each vertex. We will call this graph the \textit{dumbbell graph}. Clearly, $(G,\sigma)$ has the desired nowhere-zero $6$-flow; indeed it has a nowhere-zero $3$-flow. Let $B=\{b_1,\dots,b_l\}$ be the set of bridges of $(G,\sigma)$, where $l \geq 1$, and let $(G_i,\sigma_i)$ be the $l+1$ bridgeless components of $(G-B,\sigma|_{G-B})$, for $i \in \{1, \dots, l+1\}$. Since $(G,\sigma)$ is flow-admissible, each bridge must belong to a barbell with the property that each of the negative edges belongs to one of the unbalanced circuits of the barbell. It follows that $b_1,\ldots,b_l$ lie on a path, and that the two negative edges are contained in different end-components, say $n_1 \in E(G_1)$ and $n_2 \in E(G_{l+1})$. We claim that $l=1$. Suppose to the contrary that $l \geq 2$. Let $b_1 = x_1x_2$ and $b_l = x_{l}x_{l+1}$, where $x_i \in E(G_i)$. Reduce $(G,\sigma)$ to two smaller graphs $(H_1,\sigma_{H_1})$ and $(H_2,\sigma_{H_2})$, where $(H_1,\sigma_{H_1})$ is obtained from $(G_1,\sigma_1)$ and $(G_l,\sigma_l)$ by adding a positive edge $x_1x_{l+1}$, and $(H_2,\sigma_{H_2})$ is the all-positive graph obtained from $(G,\sigma)$ by removing $V(G_1)$ and $V(G_{l+1})$ and adding a positive edge $x_2x_{l}$. By induction hypothesis, $(H_1,\sigma_{H_1})$ has a nowhere-zero $6$-flow with the flow value $1$ on the negative edges. Hence, $x_1x_{l+1}$ has the flow value $2$. By Theorem~\ref{6_Flow} and Corollary \ref{6_Flow_1}, $(H_2,\sigma_{H_2})$ has a nowhere-zero $6$-flow with the flow value $2$ on $x_2x_{l}$. According to Observation~\ref{obser:opp}, the directions of $x_1x_{l+1}$ and $x_2x_{l}$ can be chosen appropriately so that these two nowhere-zero $6$-flows combine to the desired nowhere-zero $6$-flow on $(G,\sigma)$. Now let $b = x_1x_2$ be the only bridge of $(G,\sigma)$ and let $y_i,z_i\in V(G_i)$ be the neighbors of $x_i$ in $(G_i,\sigma_i)$ for $i \in \{1,2\}$. It follows that either $y_i \not= z_i$, or $y_i = z_i = x_i$. In the latter case $(G_i,\sigma_i)$ consists of one vertex with a negative loop. We say that $(G_i,\sigma_i)$ is a \textit{negative loop}. Suppose first that neither $(G_1,\sigma_1)$ nor $(G_2,\sigma_2)$ is a negative loop. Reduce $(G,\sigma)$ to two graphs $(H_1,\sigma_{H_1})$ and $(H_2,\sigma_{H_2})$, where $(H_i,\sigma_{H_i})$ is obtained from $(G,\sigma)$ by replacing $(G_i,\sigma_i)$ by a negative loop, for $i\in\{1,2\}$. Now the result follows easily by induction and a suitable combination of flows on $(H_i,\sigma_{H_i})$. Now assume that one component is a negative loop, say $(G_2,\sigma_2)$. The case when $(G_1,\sigma_1)$ is also a negative loop, is discussed above, hence we may assume that $(G_1,\sigma_1)$ is not a negative loop. We are going to define a nowhere-zero $6$-flow on $(G,\sigma)$ directly. Let $n_1=u_1v_1$, and let $G_1^*$ be {the} underlying graph obtained from {the} signed graph $(G_1,\sigma_1)$ by removing $n_1$ and connecting $u_1$, $v_1$ and $x_1$ {to} a new vertex $w$. We claim that $G_1^*$ is $3$-edge-connected. It is easy to see that $G_1^*$ is cubic, connected and that it does not have a bridge, because it is obtained from a $2$-edge-connected graph $(G_1,\sigma_1)$ where the deleted edge $n_1$ is replaced by a path $u_1wv_1$. Suppose to the contrary that $X\subseteq E(G_1^*)$ is a $2$-edge-cut of $G_1^*$. If $u_1$, $v_1$ and $x_1$ belong to one component of $G_1^*-X$, then $X$ is a non-separating $2$-edge-cut of $(G,\sigma)$. We may apply the $2$-edge-cut reduction on $(G,\sigma)$ with respect to $X$, and use induction hypothesis and Corollary~\ref{6_Flow_1} to obtain a contradiction. Therefore, there is one component of $G_1^*-X$ containing exactly one of $u_1$, $v_1$ and $x_1$. But then $X$ must contain exactly one edge incident to $w$, otherwise $G_1^*$ contains a bridge. Thus, $G_1^*-w=G_1-n_1$ contains a bridge. This is possible if and only if $n_1$ belongs to a $2$-edge-cut of $(G_1,\sigma_1)$, which is a non-separating $2$-edge-cut of $(G,\sigma)$, because it contains $n_1$. Similarly as above, we may use the $2$-edge-cut reduction to obtain a contradiction. We conclude that $G_1^*$ is indeed $3$-edge-connected. By Theorem~\ref{JLPT} and by Lemma~\ref{magictrick}, $G_1^*$ admits a nowhere-zero $6$-flow $(\tau_1^*,\phi^*_1)$ such that $\delta^+(w)=\{u_1w,v_1w\}$, $\delta^-(w)=\{x_1w\}$, and $\phi^*_1(u_1w)=\phi^*_1(v_1w)=1$, and $\phi^*_1(x_1w)=2$. Let $\tau$ be an orientation of $(G,\sigma)$ defined as follows: $n_1$ is extroverted, $n_2$ is introverted, $b_1\in\delta^+(x_1)$, and $\tau(e)=\tau_1^*(e)$ for every edge $e\in E(G)\cap E(G_1^*)$. Let $\phi$ be an assignment of integer values to the oriented edges of $(G,\sigma)$ defined as follows: $\phi(n_1)=\phi(n_2)=1$, $\phi(b_1)=2$, and $\phi(e)=\phi_1^*(e)$, for every edge $e\in E(G)\cap E(G_1^*)$. Then $(\tau,\phi)$ is the required nowhere-zero $6$-flow of $(G,\sigma)$. \end{proof} Using the previous theorem, we are able to prove Theorem~\ref{6_Flow} as follows. Consider a $2$-edge-connected graph $G$, and an arbitrary edge $e=uv\in E(G)$. To obtain $G'$ from $G$, remove $e$ and add new edges $uu'$, $vv'$, $l_{u'}$ and $l_{v'}$, where $u'$ and $v'$ are new vertices, and $l_{u'}$ and $l_{v'}$ are loops incident with $u'$ and $v'$, respectively. Let $\sigma'$ be a signature on $G'$ such that $\sigma'(l_{u'})=\sigma'(l_{v'})=-1$ and $\sigma'(e)=1$, for every other edge $e$ of $E(G')$. By Theorem~\ref{thm:bridges}, $(G',\sigma')$ admits an all-positive $6$-flow with the flow value $1$ on $l_{u'}$ and $l_{v'}$, and therefore, the flow value $2$ on $uu'$ and $vv'$. It is easy to see that $G$ admits a nowhere-zero $6$-flow with the flow value $2$ on $e$. Note that Theorem~\ref{thm:bridges} and Theorem~\ref{6_Flow} are not equivalent, because a stronger statement, namely Theorem~\ref{JLPT}, is used in the proof of the former one. \smallskip In the following we focus on $(G,\sigma)$ where $G$ is $3$-edge-colorable or a critical snark. Recall that a snark $G$ is \textit{critical} if $G-e$ admits a nowhere-zero $4$-flow for every edge $e$. \begin{lemma} \label{flow_value_1} Let $G$ be a cubic graph and $e_1,e_2 \in E(G)$. If $G$ is $3$-edge-colorable, then $(G,\texttt{1})$ has a nowhere-zero $4$-flow $(\tau,\phi)$ such that $\phi(e)>0$ for every $e \in E(G)$, and $\phi(e_1) = \phi(e_2) = 1$. \end{lemma} \begin{proof} Let $c:\ E(G) \to \{c_1,c_2,c_3\}$ be a $3$-edge-coloring, and let $c(e_1)=c_1$ and $c(e_2) \in \{c_1,c_2\}$. Let $\tau$ be an orientation of $G$, and let $(\tau,\phi_1)$ be a nowhere-zero $2$-flow on $c^{-1}(c_1)\cup c^{-1}(c_2)$ such that $\phi_1(e_2)=1$ and $(\tau,\phi_2)$ be a nowhere-zero $2$-flow on $c^{-1}(c_2) \cup c^{-1}(c_3)$ such that $\phi_2(e_2)=1$ if $c(e_2)=c_2$. In both cases for $c(e_2)$, $\phi$ is defined as $2\cdot\phi_2-\phi_1$. The desired flow on $(G,\sigma)$ is obtained from $(\tau,\phi)$ by reversing the direction and the value of each edge with negative value. \end{proof} \begin{theorem}\label{thm:cubic3edgecolourable} Let $(G,\sigma)$ be a flow-admissible signed cubic graph with $N_{\sigma}=\{n_1,n_2\}$. If $G$ is $3$-edge-colorable or a critical snark, then $(G,\sigma)$ has a nowhere-zero $6$-flow $(\tau,\phi)$ such that $\phi(n_1)=\phi(n_2)=1$. \end{theorem} \begin{proof} Suppose to the contrary that the statement is not true, and let $(G,\sigma)$ be a minimal counterexample. By Lemma~\ref{flow-admissible}, $(G,\sigma)$ has no negative bridge. By Lemma~\ref{lemma:p2edgecut} and Theorem~\ref{6_Flow}, $(G,\sigma)$ has no $2$-edge-cut containing both negative edges. If $(G,\sigma)$ has a $2$-edge-cut containing exactly one negative edge, then deduce a contradiction with application of the $2$-edge-cut reduction and Corollary~\ref{6_Flow_1}. In what follows we may assume that both edges of any $2$-edge-cut are positive. Let $n_1=u_1v_1$ and $n_2=u_2v_2$. Case 1: $G$ is $3$-edge-colorable. By Lemma \ref{flow_value_1}, there is a nowhere-zero $4$-flow $(\tau',\phi')$ on $(G,\texttt{1})$ such that $\phi'(n_1) = \phi'(n_2) = 1$, and $\phi'(e)>0$, for every $e\in E(G)$. Suppose, without loss of generality, that $n_1 \in \delta^+(u_1)$ and $n_2 \in \delta^+(u_2)$ in $\tau'$. Since $\phi'(n_1) = 1$, there is another edge $f=u_1v \in \delta^+(u_1)$. It follows from Lemma \ref{lemma:directeduvpath}, that there is a directed $v$-$v_2$-path of $(G,\texttt{1})$, which together with the edge $f$ forms a directed $u_1$-$v_2$-path $P$ of $(G,\texttt{1})$. We claim that $n_1 \not \in E(P)$. Otherwise either $n_1$ is a bridge, or $n_1$ belongs to a $2$-edge-cut, a contradiction. If $n_2 \not \in E(P)$, then to obtain $\tau$ from $\tau'$ reverse the direction of $h_{u_1}^{n_1}$ and $h_{v_2}^{n_2}$. Let $\phi(e) = \phi'(e) +2$ if $e \in E(P)$, and $\phi(e) = \phi'(e)$ otherwise. Then $(\tau,\phi)$ is the desired nowhere-zero $6$-flow on $(G,\sigma)$. Suppose now that $n_2\in E(P)$, for every directed $u_1$-$v_2$-path $P$ of $(G,\texttt{1})$ with $n_1\notin P$. Consider any edge-cut $X$ that contains $n_2$ and separates $u_1$ and $v_2$. Let $X$ divide $V(G)$ into two subsets $U$ and $W$, where $u_1\in U$ and $v_2\in W$. By Kirchhoff's law, the total outflow from $U$ is $0$. Since $\phi'(n_2)=1$ and $n_2$ does not belong to any $2$-edge-cut, there must be another edge of $X$ oriented from $U$ to $W$ under $\tau'$. This is possible if and only if $n_1\in X$, since every directed $u_1$-$v_2$-path $P$ of $(G,\texttt{1})$ with $n_1\notin P$ contains $n_2$. Thus, there are two edges oriented from $U$ to $V$ and they both carry the flow value 1. Therefore, there are at most two edges oriented from $V$ to $U$, and $3\leq |X| \leq 4$. By Corollary~\ref{cor:3edgecut}, $|X| = 4$, and thus, the two edges oriented from $V$ to $U$ carry the flow value 1, according to Kirchhoff's law. Let $f'=u_3v_3 \in X - N_{\sigma}$ be one of them and suppose that $f' \in \delta^+(v_3)$ in $\tau'$. Let $P'= P_1\cup f' \cup P_2$, where $P_1$ is a directed $u_1$-$u_3$-path such that $E(P_1)\cap N_{\sigma}=\emptyset$ and $P_2$ is a directed $v_3$-$v_2$-path such that $E(P_2)\cap N_{\sigma}=\emptyset$. Note that $P_1$ and $P_2$ may be trivial, but they always exist due to Kirchhoff's law. Similarly as in the case above, we define a nowhere-zero $6$-flow $(\tau,\phi)$ on $(G,\sigma)$. Note that $f' \in \delta^+(u_3)$ in $\tau$ and $\phi(f')=1$. \smallskip Case 2: $G$ is a critical snark. Hence, $(G,\texttt{1})-n_1$ admits a nowhere-zero $4$-flow $(\tau',\phi')$, and by Lemma \ref{flow_value_1}, we may assume that $\phi'(n_2)=1$, $n_2 \in \delta^+(u_2)$, and $\phi'(e)>0$ for every $e\in E(G)$. Consider a directed $u_1$-$v_2$-path $P_1$ and a directed $v_1$-$v_2$-path $P_2$ in $(G-n_1, \texttt{1})$. Since $\phi'(n_2) = 1$ and $n_2$ does not belong to any $2$-edge-cut, we may assume that $n_2\notin E(P_1)\cup E(P_2)$. Note that $P_1$ and $P_2$ are not edge-disjoint, because they share an edge whose end-vertex is $v_2$. Obtain an orientation $\tau$ of $(G,\sigma)$ by letting $n_1$ be extroverted, reversing the direction of $h_{v_2}^{n_2}$, and $\tau(h)=\tau'(h)$ for every other half-edge $h$ of $(G,\sigma)$. Let $\phi''(e) = \phi'(e) + 1$ if $e \in E(P_1)$, $\phi''(n_1) = 1$, and $\phi''(e) = \phi'(e)$ if $e \not \in E(P_1) \cup \{n_1\}$. The desired nowhere-zero $6$-flow on $(G,\sigma)$ is $(\tau,\phi)$ with $\phi(e) = \phi''(e) + 1$ if $e \in E(P_2)$, and $\phi(e) = \phi''(e)$ otherwise. \end{proof} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{General case} \label{sec:general case} In this section we prove the bound $7$ for all flow-admissible signed graphs with two negative edges, and the bound $6$ if the Tutte's conjecture is true. \begin{theorem}\label{thm:general} Let $(G,\sigma)$ be a flow-admissible signed cubic graph with two negative edges $n_1=u_1v_1$ and $n_2=u_2v_2$. Let $G^*=(V(G),E(G)\cup\{n\}-\{n_1,n_2\})$ be an unsigned graph, where $n=u_1u_2\notin E(G)$. If $G^*$ admits a nowhere-zero $k$-flow for some integer $k \geq 2$ such that $n$ receives the flow value 1, then $(G,\sigma)$ admits a nowhere-zero $(k+1)$-flow $(\tau,\phi)$ with the following properties: \begin{enumerate} \item $\phi(e)>0$, for every $e\in E(G)$, \item $\phi(n_1)=\phi(n_2)=1$, and \item there exists a $v_1$-$v_2$-path $P$ such that $\phi^{-1}(k)\subseteq E(P)$ and $\phi^{-1}(1)\cap E(P)=\emptyset$. \end{enumerate} \end{theorem} \begin{proof} Let $(\tau^*, \phi^*)$ be a nowhere-zero $k$-flow of $G^*$ with $\phi^*(e)>0$ for every $e\in E(G^*)$, $\phi^*(n)=1$ and $n \in \delta^+(u_1)$. By Lemma~\ref{lemma:directeduvpath}, there is a directed $v_2$-$v_1$-path in $G^*$. We claim that there is a directed $v_2$-$v_1$-path $P$ in $G^*-\{n\}$. If not, then all directed paths from $v_2$ contain $n$. Since $\phi^*(n)=1$, it follows that there is an edge $f$ such that $\{n, f\}$ is a $2$-edge-cut of $G^*$ which separates the two sets $\{v_1,u_2\}$ and $\{u_1,v_2\}$. Note that none of the negative edges is a bridge, otherwise the signed graph $(G,\sigma)$ would not be flow-admissible. Moreover, the negative edges do not belong to any 2-edge-cut by Lemma~\ref{lemma:p2edgecut}. Hence, $\{n_1, n_2, f\}$ is a $3$-edge-cut of $(G,\sigma)$ that contains two negative edges, contradicting Lemma \ref{lemma:noflow}, since $(G,\sigma)$ is flow-admissible. Thus, there is a directed $v_2$-$v_1$-path $P$ in $G^*-\{n\}$. We define $(\tau,\phi)$ on $(G,\sigma)$ as follows. For $e\in E(G)\cap E(G^*)$ we set $\tau(e)=\tau^*(e)$. Let $n_2$ be extroverted and $n_1$ be introverted, and let $\phi(n_2)=\phi(n_1)=1$. If $e\notin P$, then $\phi(e)=\phi^*(e)$, and if $e\in P$, then $\phi(e)=\phi^*(e)+1$. It is easy to see that $(\tau,\phi)$ is the required nowhere-zero $(k+1)$-flow. \end{proof} The previous theorem combined with the following observation provides several interesting corollaries. \begin{observation}\label{obser:G*} Let $(G,\sigma)$ be a flow-admissible signed cubic graph with two negative edges $n_1=u_1v_1$ and $n_2=u_2v_2$. Let $G^*=(V(G),E(G)\cup\{n\}-\{n_1,n_2\})$ be an unsigned graph, where $n=u_1u_2\notin E(G)$. If no $2$-edge-cut of $(G,\sigma)$ contains a negative edge, then $G^*$ is flow-admissible. \end{observation} \begin{proof} Suppose to the contrary that $G^*$ is not flow-admissible. Then $G^*$ contains a bridge $b$. If $b=n$, then either $(G,\sigma)$ has two components, each containing a negative edge, or $\{n_1,n_2\}$ is a $2$-edge-cut of $(G,\sigma)$. In the first case $(G,\sigma)$ is not flow-admissible, and in the second case there is a $2$-edge-cut of $(G,\sigma)$ containing a negative edge, a contradiction. If $b\neq n$, then $u_1$ and $u_2$ belong to the same component $H$ of $G^*-b$. If $v_1$ and $v_2$ both belong to $H$, then $b$ is a bridge of $(G,\sigma)$ with an all-positive signed graph on one side, contradicting the flow-admissibility of $(G,\sigma)$ due to Lemma~\ref{flow-admissible}. If neither $v_1$ nor $v_2$ belongs to $H$, then $\{n_1, n_2, b\}$ is a $3$-edge-cut containing two negative edges, contradicting the flow-admissibility of $(G,\sigma)$ due to Corollary~\ref{cor:3edgecut}. Suppose, finally, that one of $v_1$ and $v_2$, say $v_1$, belongs to $H$. Then $\{n_2, b\}$ is a $2$-edge-cut of $(G,\sigma)$ containing a negative edge, a contradiction. \end{proof} \begin{theorem} \label{6_7} If $(G,\sigma)$ is a flow-admissible signed cubic graph with $N_{\sigma}= \{n_1,n_2\}$, then $(G,\sigma)$ has a nowhere-zero $7$-flow $(\tau,\phi)$ such that $\phi(n_1)=\phi(n_2)=1$, and all edges with the flow value $6$ lie on a single path. \end{theorem} \begin{proof} Suppose the contrary, and let $(G,\sigma)$ be a minimal counterexample. By Theorem~\ref{thm:bridges}, we may assume that $(G,\sigma)$ is bridgeless. By Lemma~\ref{lemma:p2edgecut} and Theorem~\ref{6_Flow}, $N_{\sigma}$ does not form a $2$-edge-cut. Suppose that there is a $2$-edge-cut $X$ containing one positive and one negative edge. Let $(G_1,\sigma_1)$ and $(G_2,\texttt{1})$ be the resulting graphs of the $2$-edge-cut reduction of $(G,\sigma)$ with respect to $X$ (see Section~\ref{sec:small edge cuts} for notation). By Lemma~\ref{obser:2red}, $(G_1,\sigma_1)$ and $(G_2,\texttt{1})$ are flow-admissible. Furthermore, $(G_1,\sigma_1)$ has two negative edges and is smaller than $(G,\sigma)$. Therefore, $(G_1,\sigma_1)$ admits a nowhere-zero $7$-flow $(\tau_1,\phi_1)$ with the required properties. We may assume that $\phi_1(e)>0$, for every $e\in E(G_1)$. Note, that the added edge $f_1$ of $(G_1,\sigma_1)$ is negative and therefore, $\phi_1(f_1) = 1$. By Corollary~\ref{6_Flow_1}, there is nowhere-zero $6$-flow $(\tau_2,\phi_2)$ on $(G_2,\texttt{1})$ with $\phi_2(f_2)=\phi_1(f_1)$. By Lemma~\ref{lemma:n2edgecut}, we can combine $(\tau_1,\phi_1)$ and $(\tau_2,\phi_2)$ to define the desired nowhere-zero $7$-flow on $(G,\sigma)$, a contradiction. Finally, we may assume that every $2$-edge-cut of $(G,\sigma)$ contains only positive edges. Let $n_1 = u_1v_1$, $n_2=u_2v_2$ and let $G^*=(V(G),E(G)\cup\{n\}-\{n_1,n_2\})$ be an unsigned graph obtained from $(G,\sigma)$, where $n=u_1u_2\notin E(G)$. By Observation~\ref{obser:G*}, $G^*$ is flow-admissible, and by Theorem~\ref{6_Flow} and Corollary~\ref{6_Flow_1}, $G^*$ admits a nowhere-zero $6$-flow with the flow value 1 on $n$. We obtain a contradiction by applying Theorem~\ref{thm:general}. \end{proof} We will relate Tutte's $5$-flow conjecture and Bouchet's $6$-flow conjecture for signed graphs with two negative edges. For this we will need the following lemma. \begin{lemma} \label{fix_5-flow} Let $G$ be a cubic graph, $f \in E(G)$ and $t \in \{1,\dots,4\}$. If $G$ has a nowhere-zero $\mathbb{Z}_5$-flow, then for every possible direction of $f$, $G$ has a nowhere-zero $5$-flow $(\tau,\phi)$ with $\phi(f)=t$, and $\phi(e) > 0$ for each $e \in E(G)$. \end{lemma} \begin{proof} By Observation~\ref{obser:opp}, we only need to prove the statement for different values of $t$ irrespective of the direction of $f$. Let $(\tau,\phi)$ be a nowhere-zero $\mathbb{Z}_5$-flow on $G$. If $t\in\{1,4\}$, then we may assume that $\phi(f)=1$, otherwise we will consider $(\tau,c\cdot\phi)$, for $c\cdot\phi(f)=1$ (\,mod 5). If $t\in\{2,3\}$, then we may assume that $\phi(f)=2$, otherwise we will consider $(\tau,c\cdot\phi)$, for $c\cdot\phi(f)=2$ (\,mod 5). Let $f_1$ and $f_2$ be edges of $G$ adjacent to $f$ and incident with a common vertex $v$. We may assume that $\delta^+(v)=\{f,f_1\}$ and $\delta^-(v)=f_2$, since otherwise we revert the edge and the flow value on it. If none of $\phi(f), \phi(f_1),\phi(f_2)$ is 1, then $\phi(f)=\phi(f_1)=2$ and $\phi(f_2)=4$. Let $C$ be a directed circuit containing edges $f_1$ and $f_2$, which exists by Lemma~\ref{lemma:directeduvpath}. For the edges of $C$ revert their orientation and replace their value $\phi(e)$ by $5-\phi(e)$ to obtain a new flow. Now, the flow value of $f_2$ equals 1. Apply Lemma~\ref{magictrick} to obtain a nowhere-zero $5$-flow $(\tau_1,\phi_1)$ with $\phi_1(f)=\phi(f)$. If $\phi_1(f)\neq t$, then repeat the trick with a directed circuit $C$ for $f$ to obtain the correct value on $f$. Finally, the required flow is obtained by reversing the orientations and values of edges with the negative flow value. \end{proof} \begin{theorem} \label{5-flow_6-flow} If Tutte's $5$-flow conjecture holds true, then Bouchet's conjecture holds true for all signed graphs with two negative edges. Moreover, for any bridgeless signed graph $(G,\sigma)$ with $N_{\sigma}=\{n_1,n_2\}$, there is a nowhere-zero $6$-flow $(\tau,\phi)$ with $\phi(e)>0$ for every $e\in E(G)$ such that $\phi(n_1)=\phi(n_2)=1$, and there is a path $P$ such that $\phi^{-1}(5)\subseteq E(P)$ and $\phi^{-1}(1)\cap E(P)=\emptyset$. \end{theorem} \begin{proof} Suppose the contrary, and let $(G,\sigma)$ be a minimal signed graph with two negative edges, for which the theorem does not hold. By Theorem \ref{thm:bridges}, $(G,\sigma)$ is bridgeless. Let $X$ be a $2$-edge-cut of $(G,\sigma)$. If $X = N_{\sigma}$, then $(G,\sigma)$ has a nowhere-zero $5$-flow by Lemma \ref{lemma:p2edgecut} and by the assumption, a contradiction. Suppose that $|X \cap N_{\sigma}|=1$. Let $(G_1,\sigma_1)$ and $(G_2,\texttt{1})$ be the resulting graphs of the $2$-edge-cut reduction of $(G,\sigma)$ with respect to $X$ (see Section~\ref{sec:small edge cuts} for notation). By Lemma~\ref{obser:2red}, $(G_1,\sigma_1)$ and $(G_2,\texttt{1})$ are flow-admissible. Since $(G_1,\sigma_1)$ is smaller than $(G,\sigma)$, it admits a nowhere-zero $6$-flow $(\tau_1,\phi_1)$ with the required properties. In particular, $\phi_1(f_1) = 1$. By the assumption and by Lemma \ref{fix_5-flow}, there is a nowhere-zero $5$-flow $(\tau_2,\phi_2)$ on $(G_2,\sigma_2)$ with $\phi_2(f_2)= 1$. By Observation~\ref{obser:opp} and by Lemma \ref{lemma:n2edgecut}, we obtain a contradiction. Finally, we may assume that $|X \cap N_{\sigma}|=0$ or that $G$ is $3$-edge-connected. Let $n_i = u_iv_i$, for $i\in\{1,2\}$, and let $G^*=(V(G),E(G)\cup\{n\}-\{n_1,n_2\})$ be an unsigned graph such that $n=u_1u_2\notin E(G)$. By Observation~\ref{obser:G*}, $G^*$ is bridgeless and therefore, it has a nowhere-zero $5$-flow $(\tau,\phi)$. By Lemma \ref{fix_5-flow}, we may assume that $\phi(n)=1$. Now, the result follows from Theorem~\ref{thm:general}. \end{proof} A graph $G$ is \textit{cyclically $k$-edge-connected} if there exists no edge-cut $X$ with less than $k$ edges such that $G-X$ has two components that contain a circuit. The \textit{oddness} $\omega(G)$ of a cubic graph $G$ is the minimum number of odd circuits of any 2-factor of $G$. In \cite{Steffen_2010} it is proved that if the cyclic connectivity of a cubic graph $G$ is at least $\frac{5}{2}\omega(G) - 3$, then $F(G,\texttt{1}) \leq 5$. Clearly, if $G'$ is obtained from $G$ by subdividing an edge, then $G$ is cyclically $k$-edge-connected if and only if $G'$ cyclically $k$-edge-connected. Hence, the following corollary follows from Lemma \ref{fix_5-flow} and Theorem~\ref{thm:general}. \begin{corollary} Let $(G,\sigma)$ be a flow-admissible signed cubic graph with with two negative edges $n_1=u_1v_1$ and $n_2=u_2v_2$. Let $G^* = (V(G),E(G)\cup\{n\}-\{n_1,n_2\})$, where $n=u_1v_1\notin E(G)$. If $G^*$ is cyclically $k$-edge-connected and $k \geq \frac{5}{2}\omega(G') - 3$, then $F(G,\sigma) \leq 6$. \end{corollary} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection*{Acknowledgements} We would like to thank anonymous referees for providing the insightful comments that helped us to improve the quality of the paper. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % You do not have to use the same format for your references, but % include everything in this file. Don't use natbib please. % If you use BibTeX to create a bibliography, copy the .bbl file into here. \begin{thebibliography}{99} \bibitem{Bouchet_1983} {\sc A.~Bouchet}, \textit{Nowhere-zero integral flows on bidirected graph}, J.~Comb. Theory Ser.~B {\bf 34} (1983) 279 -- 292. \bibitem{DeVos} {\sc M.~DeVos}, \textit{Flows on bidirected graphs}, arXiv:1310.8406 [math.CO]. \bibitem{Fleischner} {\sc H.~Fleischner}, \textit{Eine gemeinsame Basis f\"ur die Theorie der eulerschen Graphen und den Satz von Petersen}, Monatsh.~Math. {\bf 81} (1976), 267 -- 278. \bibitem{JLPT} {\sc F.~Jaeger, N. Linial, C. Payan and M. Tarsi}, \textit{Group connectivity of graphs-a nonhomogeneous analogue of nowhere-zero flow properties} J.~Comb.~Theory Ser.~B {\bf 56} (1992) 165 -- 182. {\bibitem{survey}{\sc T. Kaiser, R. Luko\v tka, E. Rollov\' a} \textit{Nowhere-zero flows in signed graphs: A survey}, Lecture Notes of Seminario Interdisciplinare di Matematica \textbf{14} (2017), 85 -- 104.} \bibitem{Kochol_2011} {\sc M.~Kochol}, \textit{Three measures of edge-uncolorability}, Disc.~Math.~{\bf 311} (2011) 106 -- 108. \bibitem{Nedela_Skoviera_1996} {\sc R.~Nedela and M.~\v{S}koviera}, \textit{Decompositions and reductions of snarks}, J.~Graph Theory {\bf 22} (1996) 253 -- 279. \bibitem{MR} {\sc E. M\'a\v cajov\'a and E. Rollov\'a}, \textit{Nowhere-zero flows on signed complete and complete bipartite graphs}, J.~Graph Theory {\bf 78 (2)} (2015), 108 -- 130. \bibitem{MS} {\sc E. M\'a\v cajov\'a and M. \v Skoviera}, \textit{Determining the flow numbers of signed eulerian graphs}, Electronic Notes in Discrete Mathematics {\bf 38} (2011), 585 -- 590. \bibitem{Raspaud_Zhu_2011} {\sc A.~Raspaud and X.~Zhu}, \textit{Circular flow on signed graphs}, J.~Comb.~ Theory Ser.~B {\bf 101} (2011) 464 -- 479. \bibitem{Sch} {\sc T. Sch\"onberger}, \textit{Ein Beweis des Petersenschen Graphensatzes}, Acta Scientia Mathematica Szeged \textbf{7} (1934), 51 -- 57. \bibitem{SS} {\sc M. Schubert and E. Steffen}, \textit{Nowhere-zero flows on signed regular graphs}, {Europ. J. Combinatorics} \textbf{48} (2015), 34 -- 47. \bibitem{Sey} {\sc P. D. Seymour}, \textit{Nowhere-zero 6-flows}, J. Comb. Theory Ser. B \textbf{30} (1981), 130 -- 135. \bibitem{Steffen_1998} {\sc E.~Steffen}, \textit{Classifications and characterizations of snarks}, Discrete Math. {\bf 188} (1998) 183 -- 203. \bibitem{Steffen_2010} {\sc E.~Steffen}, \textit{Tutte's 5-flow conjecture for cyclically highly connected cubic graphs}, Discrete Math. {\bf 310} (2010) 385 -- 389. \bibitem{Tutte_1949} {\sc W. T.~Tutte}, \textit{On the imbedding of linear graphs in surfaces}, Proc.~London Math.~Soc.~{\bf 22} (1949) 474 -- 483. \bibitem{Tutte_1954} {\sc W. T.~Tutte}, \textit{A contribution to the theory of chromatic polynomials}, Canad. J. Math. {\bf 6} (1954) 80 -- 91. \bibitem{Zhu} {\sc X.~Zhu}, \textit{Circular flow number of highly edge connected signed graphs}, J. Comb. Theory Ser. B \textbf{112} (2015), 93 -- 103. \end{thebibliography} \end{document}