\frac{\alpha_{s}}{2\gamma\rho}&\frac{\alpha_{s}}{2\gamma\epsilon}&-\frac{s_{y}c_{f}\alpha_{f}\beta_{x}}{2a^{2}}&-\frac{c_{s}\alpha_{s}}{2a^{2}}&-\frac{s_{y}c_{f}\alpha_{f}\beta_{z}}{2a^{2}}&-\frac{\alpha_{f}\beta_{x}}{2a\sqrt{\rho}}&0&-\frac{\alpha_{f}\beta_{z}}{2a\sqrt{\rho}}\\\
\frac{\alpha_{s}}{2\gamma\rho}&\frac{\alpha_{s}}{2\gamma\epsilon}&\frac{s_{y}c_{f}\alpha_{f}\beta_{x}}{2a^{2}}&\frac{c_{s}\alpha_{s}}{2a^{2}}&\frac{s_{y}c_{f}\alpha_{f}\beta_{z}}{2a^{2}}&-\frac{\alpha_{f}\beta_{x}}{2a\sqrt{\rho}}&0&-\frac{\alpha_{f}\beta_{z}}{2a\sqrt{\rho}}\\\
\frac{\alpha_{f}}{2\gamma\rho}&\frac{\alpha_{f}}{2\gamma\epsilon}&\frac{s_{y}c_{s}\alpha_{s}\beta_{x}}{2a^{2}}&-\frac{c_{f}\alpha_{f}}{2a^{2}}&\frac{s_{y}c_{s}\alpha_{s}\beta_{z}}{2a^{2}}&\frac{\alpha_{s}\beta_{x}}{2a\sqrt{\rho}}&0&\frac{\alpha_{s}\beta_{z}}{2a\sqrt{\rho}}\\\
\frac{\alpha_{f}}{2\gamma\rho}&\frac{\alpha_{f}}{2\gamma\epsilon}&-\frac{s_{y}c_{s}\alpha_{s}\beta_{x}}{2a^{2}}&\frac{c_{f}\alpha_{f}}{2a^{2}}&-\frac{s_{y}c_{s}\alpha_{s}\beta_{z}}{2a^{2}}&\frac{\alpha_{s}\beta_{x}}{2a\sqrt{\rho}}&0&\frac{\alpha_{s}\beta_{z}}{2a\sqrt{\rho}}\\\
\end{bmatrix}\end{aligned}\right..$ (C3)

The left and right eigenmatrices have been verified (using Mathematica) to be
biorthonormal in the sense that
$\mathbb{S}_{y}^{-1}\mathbb{S}_{y}=\mathbb{I}$.

##  Appendix D Transverse terms; finite volume versus finite difference
approaches

The vector (in state-space) of transverse-to-$\widehat{\bm{\mathbf{z}}}$ terms
$\bm{\mathbf{C}}$ defined in Equation 11 has elements corresponding to each
primitive variable given by:

$\displaystyle C_{\rho}$
$\displaystyle=v_{x}\partial_{x}\rho+\rho\partial_{x}v_{x}+v_{y}\partial_{y}\rho+\rho\partial_{y}v_{y}$
(D1a) $\displaystyle C_{\epsilon}$
$\displaystyle=v_{x}\partial_{x}\epsilon+(\gamma-1)\epsilon\partial_{x}v_{x}+v_{y}\partial_{y}\epsilon+(\gamma-1)\epsilon\partial_{y}v_{y}$
(D1b) $\displaystyle C_{v_{x}}$
$\displaystyle=(\gamma-1)\frac{\epsilon}{\rho}\partial_{x}\rho+(\gamma-1)\partial_{x}\epsilon+v_{x}\partial_{x}v_{x}+\rho^{-1}B_{y}\partial_{x}B_{y}$
$\displaystyle\qquad\qquad\qquad\qquad+\rho^{-1}B_{z}\partial_{x}B_{z}+v_{y}\partial_{y}v_{x}-\rho^{-1}B_{y}\partial_{y}B_{x}$
(D1c) $\displaystyle C_{v_{y}}$
$\displaystyle=v_{x}\partial_{x}v_{y}-\rho^{-1}B_{x}\partial_{x}B_{y}+(\gamma-1)\frac{\epsilon}{\rho}\partial_{y}\rho+(\gamma-1)\partial_{y}\epsilon$
$\displaystyle\qquad\qquad\qquad\qquad+v_{y}\partial_{y}v_{y}+\rho^{-1}B_{x}\partial_{y}B_{x}+\rho^{-1}B_{z}\partial_{y}B_{z}$
(D1d) $\displaystyle C_{v_{z}}$
$\displaystyle=v_{x}\partial_{x}v_{z}-\rho^{-1}B_{x}\partial_{x}B_{z}+v_{y}\partial_{y}v_{z}-\rho^{-1}B_{y}\partial_{y}B_{z}+g$
(D1e) $\displaystyle C_{B_{x}}$
$\displaystyle=v_{x}\partial_{x}B_{x}-B_{y}\partial_{y}v_{x}+B_{x}\partial_{y}v_{y}+v_{y}\partial_{y}B_{x}$
(D1f) $\displaystyle C_{B_{y}}$
$\displaystyle=B_{y}\partial_{x}v_{x}-B_{x}\partial_{x}v_{y}+v_{x}\partial_{x}B_{y}+v_{y}\partial_{y}B_{y}$
(D1g) $\displaystyle C_{B_{z}}$
$\displaystyle=B_{z}\partial_{x}v_{x}-B_{x}\partial_{x}v_{z}+v_{x}\partial_{x}B_{z}+B_{z}\partial_{y}v_{y}-B_{y}\partial_{y}v_{z}+v_{y}\partial_{y}B_{z}.$
(D1h)

In the boundary layer, the transverse derivatives are treated in the same way
as derivatives in the normal direction, i.e., taking the finite volume
approach and splitting the eigensystem into positive and negative subspaces at
each interface. For the present investigation we avoided introducing
additional complications by using periodic side boundaries for all simulations
and stopping our analysis before any disturbance reached those boundaries.

On the other hand, our first attempt at implementing characteristic boundary
conditions used a finite difference approach for treating the transverse terms
in the boundary layer. This method proved to be a poor numerical
representation of MHD and also numerically unstable, which precipitated our
switch to the finite volume approach described in §5. We briefly sketch the
finite difference method as a record of what did not work, which may be of use
to other researchers.

Our unstable finite difference approximation to the transverse terms was
nearly identical to the finite volume approach of §5, except that the
eigensystems were calculated at cell centers instead of cell interfaces. The
projected characteristic speeds (i.e., the eigenvalues of each of the
transverse coefficient matrices $\mathbb{A}_{x}$ and $\mathbb{A}_{y}$) were
then used as weights for upwind finite differences. This approach is similar
to the one described in the appendix of Jiang et al. (2011), but likely
differs in the details. First, we diagonalized the transverse
($\widehat{\bm{\mathbf{x}}}$ and $\widehat{\bm{\mathbf{y}}}$) terms as at (4):

$\mathbb{A}_{x}=\mathbb{S}_{x}\mathbb{\Lambda}_{x}\mathbb{S}_{x}^{-1},\
\mathbb{A}_{y}=\mathbb{S}_{y}\mathbb{\Lambda}_{y}\mathbb{S}_{y}^{-1}.$ (D2)

The eigenvalues in $\mathbb{\Lambda}_{x}$ and $\mathbb{\Lambda}_{y}$ are the
same as in Equation (7) after the replacements specified in Appendices B and
C, e.g. for the $\widehat{\bm{\mathbf{y}}}$-direction: $v_{z}\rightarrow
v_{y}$, $c_{z,a}\rightarrow c_{y,a}(=\lvert b_{y}\rvert)$ (including inside
the definitions of $c_{s,f}$ and $\alpha_{s,f}$), and
$b_{\perp}^{2}\rightarrow b_{x}^{2}+b_{z}^{2}$; similar replacements are
applied in $\widehat{\bm{\mathbf{x}}}$.

The nonnegative and nonpositive coefficient matrices in each transverse
direction were calculated according to

$\mathbb{A}_{y+}=\mathbb{S}_{y}\frac{\mathbb{\Lambda}_{y}+\lvert\mathbb{\Lambda}_{y}\rvert}{2}\mathbb{S}_{y}^{-1},\quad\mathbb{A}_{y-}=\mathbb{S}_{y}\frac{\mathbb{\Lambda}_{y}-\lvert\mathbb{\Lambda}_{y}\rvert}{2}\mathbb{S}_{y}^{-1},$
(D3)

where $\lvert\mathbb{\Lambda}\rvert=\textsf{diag}[\lvert\lambda\rvert]$ in
each direction. As before, the positive (negative) matrix corresponds to grid-
positive (negative) propagating disturbances. Decomposed this way, the
transverse derivatives are

$\mathbb{A}_{x}\cdot\partial_{x}\bm{\mathbf{U}}+\mathbb{A}_{y}\cdot\partial_{y}\bm{\mathbf{U}}=(\mathbb{A}_{x+}+\mathbb{A}_{x-})\cdot\partial_{x}\bm{\mathbf{U}}+(\mathbb{A}_{y+}+\mathbb{A}_{y-})\cdot\partial_{y}\bm{\mathbf{U}}.$
(D4)

To approximate this equation as a finite difference, the positive and negative
eigenmatrices were evaluated at cell centers while the derivatives were taken
in the upwind direction for each of the positive and negative subspaces.
Effectively, an eigenspeed-dependent set of cell face centered derivatives
were back projected onto the cell center eigensystem to update the cell
centered state variable. Thus, we used a backward Euler finite difference
approximation projected onto the positive matrix and a forward Euler finite
difference approximation projected onto the negative matrix. In the
$\widehat{\bm{\mathbf{x}}}$ direction the approximation is

$\mathbb{A}_{x}\cdot\partial_{x}\bm{\mathbf{U}}\approx\mathbb{A}_{x+,i}\cdot\frac{\bm{\mathbf{U}}_{ijk}-\bm{\mathbf{U}}_{i-1,j,k}}{x_{i}-x_{i-1}}+\mathbb{A}_{x-,i}\cdot\frac{\bm{\mathbf{U}}_{i+1,j,k}-\bm{\mathbf{U}}_{i,j,k}}{x_{i+1}-x_{i}},$
(D5)

and in $\widehat{\bm{\mathbf{y}}}$

$\mathbb{A}_{y}\cdot\partial_{y}\bm{\mathbf{U}}\approx\mathbb{A}_{y+,j}\cdot\frac{\bm{\mathbf{U}}_{ijk}-\bm{\mathbf{U}}_{i,j-1,k}}{y_{j}-y_{j-1}}+\mathbb{A}_{y-,j}\cdot\frac{\bm{\mathbf{U}}_{i,j+1,k}-\bm{\mathbf{U}}_{i,j,k}}{y_{j+1}-y_{j}}.$
(D6)

Written out explicitly, the MHD equations were approximated in a finite
difference sense as

$\displaystyle\partial_{t}\bm{\mathbf{U}}(x_{i},y_{j},z_{k})$
$\displaystyle=-\mathbb{S}_{z}\cdot\bm{\mathbf{L}}_{z}-\mathbb{A}_{y}\cdot\partial_{y}\bm{\mathbf{U}}-\mathbb{A}_{x}\cdot\partial_{x}\bm{\mathbf{U}}-\bm{\mathbf{D}}$
(D7)
$\displaystyle\approx-(\mathbb{S}_{z}\bm{\mathbf{L}}_{z})_{ijk}-\Bigl{[}\mathbb{A}_{x+,ijk}\cdot\frac{\bm{\mathbf{U}}_{ijk}-\bm{\mathbf{U}}_{i-1,j,k}}{x_{i}-x_{i-1}}+\mathbb{A}_{x-,{ijk}}\cdot\frac{\bm{\mathbf{U}}_{i+1,j,k}-\bm{\mathbf{U}}_{i,j,k}}{x_{i+1}-x_{i}}\Bigr{]}$
$\displaystyle-\Bigl{[}\
\mathbb{A}_{y+,{ijk}}\cdot\frac{\bm{\mathbf{U}}_{ijk}-\bm{\mathbf{U}}_{i,j-1,k}}{y_{j}-y_{j-1}}+\mathbb{A}_{y-,{ijk}}\cdot\frac{\bm{\mathbf{U}}_{i,j+1,k}-\bm{\mathbf{U}}_{i,j,k}}{y_{j+1}-y_{j}}\Bigr{]}-\bm{\mathbf{D}}_{ijk},$
(D8)

where the first term, $\mathbb{S}_{z}\bm{\mathbf{L}}_{z}$, could use any
representation of the characteristic derivatives in the normal direction.

As stated, we found that the approach for transverse terms sketched above was
not numerically stable. The reason is that, individually, the positive and
negative subspace matrices $\mathbb{A}_{\pm}$ contain terms in each entry,
$A_{\pm,\sigma\zeta}$, that are not included in the MHD equations. However,
the combination $\mathbb{A}=\mathbb{A}_{+}+\mathbb{A}_{-}$ has detailed
cancellations between the nonphysical terms that, in sum, reproduce the MHD
equations. The detailed balance fails when different derivatives are projected
onto the split subspaces of a single eigensystem, or, equivalently, when a
single derivative is projected onto two different (split) eigensystems. For
example, the face-centered finite difference
$\partial_{x}\bm{\mathbf{U}}\rvert_{i+1/2}=\frac{1}{\Delta
x}(\bm{\mathbf{U}}_{i+1}-\bm{\mathbf{U}}_{i})$ is projected onto cell centered
eigensystem $\mathbb{A}_{-,i}$ to update $\bm{\mathbf{U}}_{i}$, and onto
eigensystem $\mathbb{A}_{+,i+1}$ to update $\bm{\mathbf{U}}_{i+1}$. The
combination of these projections do not produce consistent pairwise
cancellations. Taylor expanding the equations about a given location on the
grid shows that the errors are of second order.

In contrast, for the finite volume method we ultimately implemented, a single
centered derivative is always projected onto the pair of subspaces derived
from the single eigensystem at the cell interface. Even though those
projections update the two different cells on each side of the interface, they
do so in a numerically balanced way. This is why the finite volume method
works while the finite difference method fails in this case.

##  Appendix E Relation between characteristic derivatives and vertical
derivatives of primitive variables

The normal derivative of the primitive variables can be expressed directly in
terms of the characteristic derivatives in that direction. In
$\widehat{\bm{\mathbf{z}}}$ this is

$\displaystyle\partial_{z}\bm{\mathbf{U}}=\mathbb{E}^{-1}\cdot\bm{\mathbf{L}}_{z}=\mathbb{S}_{z}\mathbb{\Lambda}_{z}^{-1}\cdot\bm{\mathbf{L}}_{z}$
(17 revisited)

where the inverse matrix is

$\displaystyle\mathbb{E}^{-1}=\left.\begin{aligned}
\begin{bmatrix}0&-\frac{\rho}{\lambda_{2}}&0&0&\frac{\rho\alpha_{s}}{\lambda_{5}}&\frac{\rho\alpha_{s}}{\lambda_{6}}&\frac{\rho\alpha_{f}}{\lambda_{7}}&\frac{\rho\alpha_{f}}{\lambda_{8}}\\\
0&\frac{\epsilon}{\lambda_{2}}&0&0&\frac{(\gamma-1)\epsilon\alpha_{s}}{\lambda_{5}}&\frac{(\gamma-1)\epsilon\alpha_{s}}{\lambda_{6}}&\frac{(\gamma-1)\epsilon\alpha_{f}}{\lambda_{7}}&\frac{(\gamma-1)\epsilon\alpha_{f}}{\lambda_{8}}\\\
0&0&-\frac{\beta_{y}}{\lambda_{3}}&\frac{\beta_{y}}{\lambda_{4}}&-\frac{c_{f}\alpha_{f}\beta_{x}}{\lambda_{5}s_{z}}&\frac{c_{f}\alpha_{f}\beta_{x}}{\lambda_{6}s_{z}}&\frac{c_{s}\alpha_{s}\beta_{x}}{\lambda_{7}s_{z}}&-\frac{c_{s}\alpha_{s}\beta_{x}}{\lambda_{8}s_{z}}\\\
0&0&\frac{\beta_{x}}{\lambda_{3}}&-\frac{\beta_{x}}{\lambda_{4}}&-\frac{c_{f}\alpha_{f}\beta_{y}}{\lambda_{5}s_{z}}&\frac{c_{f}\alpha_{f}\beta_{y}}{\lambda_{6}s_{z}}&\frac{c_{s}\alpha_{s}\beta_{y}}{\lambda_{7}s_{z}}&-\frac{c_{s}\alpha_{s}\beta_{y}}{\lambda_{8}s_{z}}\\\
0&0&0&0&-\frac{c_{s}\alpha_{s}}{\lambda_{5}}&\frac{c_{s}\alpha_{s}}{\lambda_{6}}&-\frac{c_{f}\alpha_{f}}{\lambda_{7}}&\frac{c_{f}\alpha_{f}}{\lambda_{8}}\\\
0&0&-\frac{\sqrt{\rho}\beta_{y}}{\lambda_{3}s_{z}}&-\frac{\sqrt{\rho}\beta_{y}}{\lambda_{4}s_{z}}&-\frac{a\sqrt{\rho}\alpha_{f}\beta_{x}}{\lambda_{5}}&-\frac{a\sqrt{\rho}\alpha_{f}\beta_{x}}{\lambda_{6}}&\frac{a\sqrt{\rho}\alpha_{s}\beta_{x}}{\lambda_{7}}&\frac{a\sqrt{\rho}\alpha_{s}\beta_{x}}{\lambda_{8}}\\\
0&0&\frac{\sqrt{\rho}\beta_{x}}{\lambda_{3}s_{z}}&\frac{\sqrt{\rho}\beta_{x}}{\lambda_{4}s_{z}}&-\frac{a\sqrt{\rho}\alpha_{f}\beta_{y}}{\lambda_{5}}&-\frac{a\sqrt{\rho}\alpha_{f}\beta_{y}}{\lambda_{6}}&\frac{a\sqrt{\rho}\alpha_{s}\beta_{y}}{\lambda_{7}}&\frac{a\sqrt{\rho}\alpha_{s}\beta_{y}}{\lambda_{8}}\\\
\frac{1}{\lambda_{1}}&0&0&0&0&0&0&0\end{bmatrix}\end{aligned}\right.$ (E1)

Carrying through the matrix multiplication, the vertical derivatives of
primitive variables are given explicitly as

$\displaystyle\partial_{z}\rho$
$\displaystyle=-\frac{\rho}{\lambda_{2}}L_{2}+\frac{\rho\alpha_{s}}{\lambda_{5}}L_{5}+\frac{\rho\alpha_{s}}{\lambda_{6}}L_{6}+\frac{\rho\alpha_{f}}{\lambda_{7}}L_{7}+\frac{\rho\alpha_{f}}{\lambda_{8}}L_{8}$
(E2a) $\displaystyle\partial_{z}\epsilon$
$\displaystyle=\frac{\epsilon}{\lambda_{2}}L_{2}+\frac{(\gamma-1)\epsilon\alpha_{s}}{\lambda_{5}}L_{5}+\frac{(\gamma-1)\epsilon\alpha_{s}}{\lambda_{6}}L_{6}+\frac{(\gamma-1)\epsilon\alpha_{f}}{\lambda_{7}}L_{7}+\frac{(\gamma-1)\epsilon\alpha_{f}}{\lambda_{8}}L_{8}$
(E2b) $\displaystyle\partial_{z}v_{x}$
$\displaystyle=-\frac{\beta_{y}}{\lambda_{3}}L_{3}+\frac{\beta_{y}}{\lambda_{4}}L_{4}-\frac{c_{f}\alpha_{f}\beta_{x}}{\lambda_{5}s_{z}}L_{5}+\frac{c_{f}\alpha_{f}\beta_{x}}{\lambda_{6}s_{z}}L_{6}+\frac{c_{s}\alpha_{s}\beta_{x}}{\lambda_{7}s_{z}}L_{7}-\frac{c_{s}\alpha_{s}\beta_{x}}{\lambda_{8}s_{z}}L_{8}$
(E2c) $\displaystyle\partial_{z}v_{y}$
$\displaystyle=\frac{\beta_{x}}{\lambda_{3}}L_{3}-\frac{\beta_{x}}{\lambda_{4}}L_{4}-\frac{c_{f}\alpha_{f}\beta_{y}}{\lambda_{5}s_{z}}L_{5}+\frac{c_{f}\alpha_{f}\beta_{y}}{\lambda_{6}s_{z}}L_{6}+\frac{c_{s}\alpha_{s}\beta_{y}}{\lambda_{7}s_{z}}L_{7}-\frac{c_{s}\alpha_{s}\beta_{y}}{\lambda_{8}s_{z}}L_{8}$
(E2d) $\displaystyle\partial_{z}v_{z}$
$\displaystyle=-\frac{c_{s}\alpha_{s}}{\lambda_{5}}L_{5}+\frac{c_{s}\alpha_{s}}{\lambda_{6}}L_{6}-\frac{c_{f}\alpha_{f}}{\lambda_{7}}L_{7}+\frac{c_{f}\alpha_{f}}{\lambda_{8}}L_{8}$
(E2e) $\displaystyle\partial_{z}B_{x}$
$\displaystyle=-\frac{\sqrt{\rho}\beta_{y}}{\lambda_{3}s_{z}}L_{3}-\frac{\sqrt{\rho}\beta_{y}}{\lambda_{4}s_{z}}L_{4}-\frac{a\sqrt{\rho}\alpha_{f}\beta_{x}}{\lambda_{5}}L_{5}-\frac{a\sqrt{\rho}\alpha_{f}\beta_{x}}{\lambda_{6}}L_{6}+\frac{a\sqrt{\rho}\alpha_{s}\beta_{x}}{\lambda_{7}}L_{7}+\frac{a\sqrt{\rho}\alpha_{s}\beta_{x}}{\lambda_{8}}L_{8}$
(E2f) $\displaystyle\partial_{z}B_{y}$
$\displaystyle=\frac{\sqrt{\rho}\beta_{x}}{\lambda_{3}s_{z}}L_{3}+\frac{\sqrt{\rho}\beta_{x}}{\lambda_{4}s_{z}}L_{4}-\frac{a\sqrt{\rho}\alpha_{f}\beta_{y}}{\lambda_{5}}L_{5}-\frac{a\sqrt{\rho}\alpha_{f}\beta_{y}}{\lambda_{6}}L_{6}+\frac{a\sqrt{\rho}\alpha_{s}\beta_{y}}{\lambda_{7}}L_{7}+\frac{a\sqrt{\rho}\alpha_{s}\beta_{y}}{\lambda_{8}}L_{8}$
(E2g) $\displaystyle\partial_{z}B_{z}$
$\displaystyle=\frac{1}{\lambda_{1}}L_{1}.$ (E2h)

Suppose one has determined an estimate for the incoming characteristics by
some means. Then, Equations (E2) could be used to form a simple finite-
difference approximation to set primitive variables in the ghost cell layer
using the values of the interior cell:

$\displaystyle\partial_{z}\bm{\mathbf{U}}\approx\frac{\bm{\mathbf{U}}_{0}-\bm{\mathbf{U}}{-1}}{\Delta
z}=\mathbb{E}^{-1}\bm{\mathbf{L}}_{z}$ (E3)
$\displaystyle\Longrightarrow\bm{\mathbf{U}}_{-1}\approx\bm{\mathbf{U}}_{0}-\Delta
z\mathbb{E}^{-1}\bm{\mathbf{L}}_{z}.$ (E4)

A two dimensional version of this method for setting boundary conditions for a
hydrodynamic system was described and implemented in Thompson (1987) and
Thompson (1990). Our own implementation worked quite well for a variety of one
dimensional MHD problems but failed in higher dimensions when coupled to the
finite-difference version of the transverse terms as described in the previous
Appendix §D. Again, this ultimately led us to implement a finite volume
version of characteristic boundaries. Despite that failure of the finite
difference implementation, we have found that the simple link between the
characteristic and vertical derivatives is a useful illustrative concept, and
thus have included it here.

##  Appendix F Details of the simulations

###  F.1 Description of the spheromak initial condition

We define the spheromak following Rosenbluth & Bussac (1979). In normalized
units, the magnetic field $\bm{\mathbf{B}}$ is a linear force-free field
satisfying

$\bm{\mathbf{j}}=\kappa\bm{\mathbf{B}},$ (F1)

where $\bm{\mathbf{j}}=\nabla\times\bm{\mathbf{B}}$ is the current density and
$\kappa$ is a scalar constant. Taking the curl of the current and using
$\nabla\cdot\bm{\mathbf{B}}=0$ we find

$\displaystyle\nabla\times\bm{\mathbf{j}}=-\nabla^{2}\bm{\mathbf{B}}=\nabla\times(\kappa\bm{\mathbf{B}})=\kappa\nabla\times\bm{\mathbf{B}}=\kappa^{2}\bm{\mathbf{B}},$
(F2) so that
$\displaystyle\nabla^{2}\bm{\mathbf{B}}+\kappa^{2}\bm{\mathbf{B}}=\bm{\mathbf{0}}.$
(F3)

The magnetic field therefore satisfies the vector Helmholtz equation. The
magnetic field $\bm{\mathbf{B}}$ can be expressed in terms of the vector
potential $\bm{\mathbf{A}}$ through
$\bm{\mathbf{B}}=\nabla\times\bm{\mathbf{A}}$. We use a vector potential
written in terms of a scalar field $\psi$,

$\displaystyle\bm{\mathbf{A}}=\bm{\mathbf{r}}\times\frac{\bm{\mathbf{\nabla}}\psi}{\kappa}-\bm{\mathbf{r}}\psi,$
(F4)

so that the resulting magnetic field is

$\bm{\mathbf{B}}=\bm{\mathbf{\nabla}}\times\bm{\mathbf{A}}=\bm{\mathbf{\nabla}}\times\Bigl{(}\bm{\mathbf{r}}\times\frac{\bm{\mathbf{\nabla}}\psi}{\kappa}\Bigr{)}-\bm{\mathbf{r}}\times\bm{\mathbf{\nabla}}\psi.$
(F5)

The scalar field $\psi$ solves the scalar Helmholtz equation in spherical
coordinates (Morse & Feshbach, 1953, §13.1, p.1766),

$\displaystyle\nabla^{2}\psi+\kappa^{2}\psi=0,$ (F6)

and has solutions

$\psi_{m}^{n}=j_{m}(\kappa r)P_{m}^{n}(\cos\theta)e^{in\phi},$ (F7)

where $j_{m}(\kappa r)$ are the spherical Bessel functions of the first kind
(Abramowitz & Stegun, 1964, §10.1.1) and $P_{m}^{n}(\cos\theta)$ are the
associated Legendre functions of the first kind (Abramowitz & Stegun, 1964,
§8.1.1). Here, the spherical coordinates $(r,\theta,\phi)$ are defined by
$r^{2}=x^{2}+y^{2}+z^{2}$, the polar angle
$\theta=\arctan\frac{y^{2}+z^{2}}{x}$, and the azimuthal angle
$\phi=\arctan\frac{z}{y}$. Thus, $x=r\cos\theta,\ y=r\sin\theta\cos\phi$, and
$z=r\sin\theta\sin\phi$. These differ from the more typical spherical
coordinates, which set $\widehat{\bm{\mathbf{z}}}$ as the axis of symmetry, by
the cyclic permutation $(x\rightarrow y,y\rightarrow z,z\rightarrow x)$. This
choice orients the spheromak so that expansion in $\widehat{\bm{\mathbf{z}}}$
mimics some properties of emerging active regions. These solutions for the
vector Helmholtz equation can be verified by direct substitution of Equations
(F7) and (F6) into (F5) and (F3).

Our simulation is initialized using the ground state axisymmetric spheromak,
defined with $m=1,\ n=0$:

$\displaystyle\psi_{1}^{0}$ $\displaystyle=B_{0}j_{1}(\kappa
r)P_{1}^{0}(\cos\theta)$ (F8) $\displaystyle=B_{0}\Bigl{(}\frac{\sin\kappa
r}{\kappa^{2}r^{2}}-\frac{\cos\kappa r}{\kappa
r}\Bigr{)}\sqrt{\frac{3}{4\pi}}\cos\theta.$ (F9)

$B_{0}$ is a scalar coefficient that gives the amplitude of the spheromak’s
magnetic field. The vector potential is thus

$\displaystyle\bm{\mathbf{A}}_{1}^{0}$
$\displaystyle=-B_{0}r\Bigl{(}\frac{\sin\kappa
r}{\kappa^{2}r^{2}}-\frac{\cos\kappa r}{\kappa
r}\Bigr{)}\sqrt{\frac{3}{4\pi}}\cos\theta\widehat{\bm{\mathbf{r}}}-\frac{B_{0}}{\kappa}\Bigl{(}\frac{\sin\kappa
r}{\kappa^{2}r^{2}}-\frac{\cos\kappa r}{\kappa
r}\Bigr{)}\sqrt{\frac{3}{4\pi}}\sin\theta\widehat{\bm{\mathbf{\phi}}}.$ (F10)

Transformed to the Cartesian coordinates used in the LaRe3D MHD code, (i.e.,
$\bm{\mathbf{A}}\rightarrow\\{A_{x},A_{y},A_{z}\\}$) the vector potential is

$\displaystyle\bm{\mathbf{A}}_{1}^{0}(x,y,z)=B_{0}\sqrt{\frac{3}{4\pi}}\Bigl{(}\frac{\cos\kappa
r}{\kappa^{2}r^{2}}-\frac{\sin\kappa
r}{\kappa^{3}r^{3}}\Bigr{)}\bigl{\\{}\kappa x^{2},\kappa xy-z,\kappa
xz+y\bigr{\\}}.$ (F11)

The spheromak solution contains a flux surface at the first zero of the Bessel
function $j_{1}(\kappa r)$, where $\kappa r\approx 4.4934$, which divides the
volume into isolated flux domains. The radial component of the magnetic field
is zero at this surface, and so it is convenient to set $\bm{\mathbf{B}}=0$
outside this surface because one can formally do so without generating
monopoles in the solution. We therefore set $\kappa\approx 4.4934$ so that the
first zero of the Bessel function occurs at $r=1$, and then set
$\bm{\mathbf{A}}=\bm{\mathbf{0}}$ outside this surface in our initial
condition. This choice of boundary conditions for the spheromak solution
creates a closed magnetic subvolume surrounded by a field-free plasma with a
tangential discontinuity (current sheet) across the $r=1$ flux boundary.
Hereafter we refer to the magnetized portion of the plasma, initially at
$r\leq 1$ as “the spheromak,” though technically the classical spheromak
described by Rosenbluth & Bussac (1979) has a vacuum magnetic field that
extends to infinity and a magnetized plasma confined within the first zero of
the Bessel function.

Numerically, each component of the vector potential is defined at the
corresponding edges of a computational cell (e.g., $A_{x}$ is defined on the
for $x$-oriented edges in a cell). The magnetic field is initialized using the
finite–difference version of $\bm{\mathbf{B}}=\nabla\times\bm{\mathbf{A}}$,
which gives the magnetic field magnitude in the direction normal to each cell
face. LaRe3D’s finite difference scheme then ensures that the solenoidal
condition $\nabla\cdot\bm{\mathbf{B}}=0$ is satisfied in the initial condition
to numerical roundoff, and LaRe3D’s flux-constrained-transport scheme ensures
that the initial distribution of $\nabla\cdot\bm{\mathbf{B}}$ is constant in
time to numerical roundoff, i.e., at roughly $\mathcal{O}(10^{-14})$. However,
LaRe3D’s Cartesian geometry means that the above precision does not hold at
the $r=1$ spherical edge of the spheromak because we set the vector potential
to zero outside of this surface. To remedy the issue we introduce a smoothing
function $f(r;e)$ that leaves the spheromak solution unchanged for $r<1-e$ and
has continuous zeroth and first derivatives for $1-e<r<1+e$:

$\displaystyle f(r;e)=\begin{cases}1&,r\leq 1-e\\\
\frac{(1+e-r)^{2}(-1+2e+r)}{4e^{3}}&,1-e<r<1+e\\\ 0&,1+e\leq r\end{cases}$
(F12)

We then let $\bm{\mathbf{A}}\rightarrow f(r)\bm{\mathbf{A}}$. The resulting
magnetic field is modified near the spheromak boundary to be
$\bm{\mathbf{B}}=\nabla\times\bm{\mathbf{A}}=f\nabla\times\bm{\mathbf{A}}+\nabla
f\times\bm{\mathbf{A}}$. The effect of the smoothing is to add a small
perturbation to the $\widehat{\bm{\mathbf{\theta}}}$ component of
$\bm{\mathbf{B}}$ near the $r=1$ boundary of the spheromak, and drop both
$\bm{\mathbf{A}}$ and $\bm{\mathbf{B}}$ smoothly to $\bm{\mathbf{0}}$ for
$r>1+e$. We have found that a width of $e=3$ simulation cells is sufficient to
ensure $\nabla\cdot\bm{\mathbf{B}}=0$ to numerical roundoff everywhere, and
again, LaRe3D’s flux-constrained-transport scheme maintains this level of
precision for the remainder of every simulation.

The initial magnetic configuration is visualized in the top left panel of
Figure 5 by tracing field lines initiated at two sets of seed points. The
first set of seed points are located near the toroidal axis of the spheromak
($x\approx 0,\ \sqrt{y^{2}+z^{2}}\approx 0.6$), and the second set near its
symmetry axis ($\lvert x\rvert<1,\ \sqrt{y^{2}+z^{2}}\approx 0$). The field
lines near the toroidal axis loop dominantly in the $y-z$ plane while orbiting
that axis at a constant minor radius; these form the toroidal core of the
spheromak. Field lines initiated near the symmetry axis of the spheromak
(i.e., along the $x$ axis) instead form loops primarily in planes
perpendicular to the axis of the toridal core, closing along the spheromak’s
outer $r=1$) surface. Intermediate field lines vary smoothly between these two
configurations. The later times in Figure 5 also show field lines traced from
a third set of seed points that have $z=1.25$ (just above the driving plane at
$z_{b}=1.09$; see next section) and are initiated within a circle of radius
$1$ centered on $x=y=0$. To ease visual comparison between different
simulations, the top-down perspective of Figure 6 only shows this third set of
field lines, and we chose the z=1.25 plane for initialization as opposed to
the driving plane so that one field line passing through $(x,y)=(0,0)$ would
be visible in Figure 6. The location of the seed points are constant in time,
so the visualized field lines at different times highlight diverse regions of
the spheromak (a more involved calculation, with the seed points advected with
the fluid flow, could also be performed, but we have not undertaken that
complication here).

Because we set the field outside the $r=1$ flux surface to zero, our spheromak
is initially unbalanced and will expand. However, we found that expansion to
be rather minimal even for relative low background pressures. Therefore, in
order to achieve substantial expansion, we embed the spheromak in an initially
non-uniform gas pressure according to

$P(x,y,z)=P_{\rm 0}+P_{\rm 1}\left(\frac{B^{2}}{1+r}\right),$ (F13)

with $P_{\rm 0}$ the background gas pressure and $P_{\rm 1}$ perturbation
amplitude of the increased gas pressure internal to the spheromak. While any
gas pressure increase from the outside to the inside of the spheromak will
cause some expansion, the additional dependence on magnetic field strength and
radial distance from the center of the spheromak encourages a gradual
expansion (i.e., keeping $\lvert\bm{\mathbf{v}}\rvert\lesssim a$, the fastest
propagation speed in the surrounding field-free plasma). The resulting ground
truth simulation then produces a spheromak that expands from the initial
condition to a new, larger configuration that is close to equilibrium.

###  F.2 Simulation setup, initial condition, and overview

For the _GT_ simulation we set $N_{x}=N_{y}=256$ and $N_{z}=192$ cells. The
dimensionless domain lengths are $L_{x}=L_{y}=8.0$ and $L_{z}=6.0$ and the
simulation extends to $\pm 4.0$ in the $x$ and $y$ directions, and has
$-2.0\leq z\leq 4.0$ in the $z$ direction, with all domain boundaries defined
at cell faces. The boundary conditions on the _GT_ simulation are set to be
periodic in $x$, $y$, and $z$. The spheromak is centered on the origin, has a
radius of $1.0$, and has its symmetry axis in the $\widehat{\bm{\mathbf{x}}}$
direction.

The normalization coefficients for the MHD equations are given in SI units as
$L_{N}=1\,\mathrm{m}$, $\rho_{N}=1\,\mathrm{kg}\,\mathrm{m}^{-3}$, and
$B_{N}=\sqrt{4\pi\times 10^{-7}}T$, i.e., the latter is scaled by the square
root of the amplitude of the permeability of free space in SI units. As
described in the text following Equation 1, all other normalization constants
can be derived from these three. For instance, the normalizing velocity is
$V_{N}=1\,\mathrm{m}\,\mathrm{s}^{-1}$. Then, in normalized units, the initial
condition has a uniform density of $\rho_{0}=0.1$, a background pressure of
$P_{\rm 0}=6.667\times 10^{-3}$ and perturbation amplitude $P_{\rm 1}=1.0$ in
(F13), and a spheromak magnetic field amplitude of $B_{0}=2.0$ in (F11). These
initial conditions make the total Alfvén crossing time across the initial
spheromak about $t=2.25$.

The _Data-Driven_ simulations span $-2.0\leq x,y\leq 2.0$ and $1.125<z<4.0$
(again corresponding to cell faces). The resolution is the same as the _GT_
simulation, so both the _Driving_ and _Data-Driven_ simulations have
$N_{x}=N_{y}=128$ and the latter has $N_{z}=92$ cells (recall the _Driving_
simulation has $N_{z}=4$, always). From the _GT_ simulation we extract the
cell-center averaged data from the $z=z_{b}=1.109375$ plane (i.e., the $100$th
$z-$cell of the _GT_ simulation) at every Courant step, and use this as input
to the _Driving_ (and therefore _Data-Driven_) simulations.

##  Appendix G Comparison to potential and nonlinear force free extrapolations

Figure 11: Comparison between a potential field extrapolation (left column),
the result of data driving using a driving cadence of $\Delta t=20\delta t$
(center column), and a nonlinear force free field extrapolation using the
optimization code provided by Thomas Wiegelmann (right). The top and bottom
rows show two different perspectives. The extrapolation time $t=1.55t_{N}$ is
at courant step 380, near the end of the spheromak’s expansion. Figure 12:
Same as Figure 11, but including field lines initiated near the edge of the
emerged portion of the spheromak.

Any single-time extrapolation of the magnetic field will leave out important
dynamic information that, in general, will have a major effect on the state of
the corona. Indeed, that is one major motivation to develop data-driven
boundary conditions. Nonetheless, static extrapolations are the simplest
possible reconstructions of the coronal magnetic field that can be made,
require the fewest computational resources, and are therefore the most often
employed method to model the coronal field and interpret coronal observations.
For that reason we include a comparison of two such extrapolation methods to
our MHD based _Data-Driven_ solution. Note that both extrapolations use the
limit in which electromagnetic forces are dominant and material forces are
negligible, and hence do not provide any information about the plasma
quantities. We therefore must neglect those quantities in the following
discussion.

In Figures 11 and 12 we compare a potential field extrapolation (left column)
and a nonlinear force free field extrapolation (right column) to the magnetic
field resulting from the _Data-Driven_ simulation using $\Delta t=20\delta t$
(center). The two Figures have the same perspectives but highlight field lines
closer to the center of the spheromak (Figure 11) and further towards its edge
(Figure 12). Recall from the discussion of Figures 5 and 6 that the magnetic
field produced by the _Data-Driven_ simulation with 20$\delta t$ is nearly
indistinguishable from the _GT_ field, so we have not included the latter
here. The seed points of the field lines are the same for all panels, so
differences between the left or right columns relative to the center column
represent errors in the extrapolations.

Both the potential field and the nonlinear force free field were generated
using the optimization code provided by Thomas Wiegelmann, and described in
Wiegelmann (2004), Wiegelmann & Inhester (2010), and Wiegelmann et al. (2012).
The potential field extrapolation uses the normal field component $B_{z}$ in
the driving layer as a bottom boundary condition, while the optimization-based
nonlinear force free field extrapolation also incorporates the horizontal
fields $B_{x}$ and $B_{y}$ in the boundary layer. We did not attempt an
exhaustive search of code parameters in order to find the best fit between the
field in the _GT_ simulation and the results of the extrapolations. This is
how extrapolation codes must often be used in practice when comparison to a
ground truth is not possible, and side boundaries can typically only be
modeled as periodic, perfectly conducting, or perhaps some asymptotic
approach.

This potential field was computed using a version of FFT approach of
Alissandrakis (1981) included in the optimization code171717We do note that a
simple Green’s function method, also included in Wiegelmann’s optimization
code, produced similar results. Indeed, Alissandrakis (1981) notes the
equivalence of the approaches when the boundary conditions are properly
specified). As such, the boundary conditions assume periodicity in the
horizontal directions and exponential decay in the vertical direction. This
produces a field that does not close locally, even though the region is in
fact flux balanced and magnetically isolated: the _GT_ solution contains a
sheath current sheet inside the domain that fully shields the field. Instead,
erroneous magnetic connections outside the domain can be seen in the left hand
columns of the figures where field lines initiated near the edge of spheromak
in the potential field extrapolation run into the boundary of the
computational box. In the _GT_ simulation (or the nearly indistinguishable
_Data-Driven_ field shown here), the field never reaches the sides of the
computational box in any direction, but instead is confined to a small
subregion of the full numerical domain. This is because, dynamically, the
spheromak expands into a field free region and includes tangential current
sheet bounding the edge of the magnetic spheromak. At the end of the _GT_
simulation, the magnetic field embedded in the blast wave has expanded and the
plasma density and pressure have developed gradients such that the system
reaches a roughly equilibrium state. Neither of the extrapolations, which are
fundamentally static solutions, can incorporate knowledge of this dynamic
evolution.

We therefore see that the potential field volume-filling, as required by the
assumption that no currents exist with the domain (which would be required to
shield the sources of the field that is imposed at the lower boundary). The
NLFF field also fills the volume, but qualitatively less so in the following
sense: the magnitude of $B$ drops off much more rapidly in the NLFF field
extrapolation compared to the potential field solution for the given boundary
conditions in which the field amplitude goes to zero as $z\rightarrow\infty$.
This is apparent in the more confined loops for the NLFF field in the right
columns of the Figures, especially for those field lines initiated near the
edge of the spheromak and shown in the right columns of Figure 12. In this
sense, the NLFF extrapolation does produce a qualitatively better
approximation to the true solution compared to the potential extrapolation, at
least in this case (see, however, De Rosa et al., 2009, for a discussion of
applicability of NLFF field extrapolations to the solar corona in general and
the metrics by which they may be assessed). This is, perhaps, expected when
the true solution contains currents throughout the solution volume, which are
allowed in a NLFF field, whereas a potential field is current-free in the
solution volume by definition.

The reality is that the final state of the _GT_ simulation and/or _Data-
Driven_ simulation is neither current free nor force free: while the spheromak
in the initial condition is a _linear_ force free field, it evolves away from
that configuration due to being embedded in the blast wave, and the final
state includes non-zero Lorentz forces that are approximately balanced by
pressure gradient forces. This fact severely compromises the NLFF
extrapolation’s ability to reproduce the ground truth field (Peter et al.,
2015). The NLFF extrapolation cannot represent this type of force-balance,
which partially explains why the NLFF extrapolation produces a greater
expansion of field compared to the _GT_ solution (or $\Delta t=20\delta t{}$
_Data-Driven_ solution shown in the figures). Another aspect is that both the
potential and the NLFF field extrapolations assume a static configuration and
therefore have no notion of the speed at which real information can physically
propagate through a system, information that includes the propagation of the
shielding current sheet the defines the boundary between the expanding
spheromak and the surrounding plasma. Our method of boundary driving allows
the _Data-Driven_ simulation to self-consistently reproduce the shielding
current sheet in the volume away from the boundary, outside of which the
solution remains field-free. This holds even in the case where $\Delta
t=100\delta t$, far exceeding the critical driving cadence of $\Delta t\approx
40\delta t$, and when other aspects of the driven solution are severely
compromised. Instead, the NLFF extrapolation produces a field that is
substantially more “puffed up” than the true solution, and always contains
erroneous magnetic connectivity to the external universe. This demonstrates
one way in which the dynamical constraint imposed by the observed temporal
evolution of the lower boundary, coupled to a true dynamical model of the full
system’s evolution, is key to allowing the _Data-Driven_ simulation to produce
a more faithful representation of the field of the expanded spheromak,
including the outer edge of the emerged field’s region of influence.


# A note on shortest circuit cover of 3-edge colorable cubic signed
graphs††thanks: The work was supported by NNSF of China (No. 12071453) and
Anhui Initiative in Quantum Information Technologies (AHY150200) and the
National Key R and D Program of China(2020YFA0713100).

Ronggui Xua, Jiaao Lib Xinmin Houa,c
aSchool of Mathematical Sciences
University of Science and Technology of China, Hefei, Anhui 230026, China.
bSchool of Mathematical Sciences
Nankai University, Tianjin 300071, China
cCAS Key Laboratory of Wu Wen-Tsun Mathematics
University of Science and Technology of China, Hefei, Anhui 230026, China.

###### Abstract

A sign-circuit cover $\mathcal{F}$ of a signed graph $(G,\sigma)$ is a family
of sign-circuits which covers all edges of $(G,\sigma)$. The shortest sign-
circuit cover problem was initiated by Má$\check{\text{c}}$ajová, Raspaud,
Rollová, and Škoviera (JGT 2016) and received many attentions in recent years.
In this paper, we show that every flow-admissible 3-edge colorable cubic
signed graph $(G,\sigma)$ has a sign-circuit cover with length at most
$\frac{20}{9}|E(G)|$.

##  1 Introduction

In this paper, graphs may have parallel edges and loops. A circuit is a
connected $2$-regular graph. A graph is even if every vertex has even degree,
and an Eulerian graph is a connected even graph. A circuit cover $\mathcal{C}$
of a graph is a family of circuits which covers all edges of $G$. We call
$\mathcal{C}$ a circuit $k$-cover of $G$ if $\mathcal{C}$ covers every edge of
$G$ exactly $k$ times. The length of a circuit cover $\mathcal{C}$ is defined
as $\ell(\mathcal{C})=\sum_{C\in\mathcal{C}}|E(C)|$. Determining the shortest
length of a circuit cover of a graph $G$ (denoted by
$scc(G)=\min\\{\ell(\mathcal{C}):\mathcal{C}\leavevmode\nobreak\ \text{is a
circuit cover}\\}$) is a classic optimization problem initiated by Itai,
Lipton, Papadimitriou, and Rodeh [8]. Thomassen [9] showed that it is NP-
complete to determine whether a bridgeless graph has a circuit cover with
length at most $k$ for a given integer $k$. A well-known conjecture, the
Shortest Circuit Cover Conjecture, was proposed by Alon and Tarsi [1] as
follows.

######  Conjecture 1.1 (Shortest Circuit Cover Conjecture).

For any $2$-edge-connected graph $G$, $scc(G)\leq\frac{7}{5}|E(G)|$.

The upper bound is achieved by the Petersen graph. Jamshy and Tarsi [10]
proved that Conjecture 1.1 implies the well-known Cycle Double Cover
Conjecture proposed by Seymour [11] and Szekeres [12]. The best known general
result about Conjecture 1.1 is obtained by Bermond, Jackson, Jaeger [13] and
Alon, Tarsi [1], independently.

######  Theorem 1.2 (Bermond, Jackson and Jaeger [13], Alon and Tarsi [1]).

Let $G$ be a $2$-edge-connected graph. Then $scc(G)\leq\frac{5}{3}|E(G)|$.

Several improvements of this upper bound for cubic graphs $G$ have been made
in literature. Specifically, Jackson [19] showed that
$scc(G)\leq\frac{64}{39}|E(G)|$ and Fan [16] later showed that
$scc(G)\leq\frac{44}{27}|E(G)|$, Kaiser, Tomáš, Král, Lidickỳ, Nejedlỳ, and
Šámal [20] improved Fan’s result to $scc(G)\leq\frac{34}{21}|E(G)|$ and Hou
and Zhang [4] proved that $scc(G)\leq\frac{8}{5}|E(G)|$ if $G$ has girth at
least 7 and $scc(G)\leq\frac{361}{225}|E(G)|$ if all 5-circuits of $G$ are
disjoint. Recently, Lukoťka [14] showed that $scc(G)\leq\frac{212}{135}|E(G)|$
for all $2$-edge-connected cubic graphs $G$.

A signed graph $(G,\sigma)$ is a graph $G$ associated with a mapping
$\sigma:E(G)\rightarrow\\{+1,-1\\}$. An edge $e\in E(G)$ is positive if
$\sigma(e)=1$ and negative if $\sigma(e)=-1$. A signed graph $G$ is called
positive if $G$ contains even number of negative edges and otherwise called
negative. In a signed graph, a circuit with an even number of negative edges
is called a balanced circuit, and otherwise we call it an unbalanced circuit.
A barbell is a signed graph consisting of two unbalanced circuits joined by a
(possibly trivial) path, intersecting with the circuits only at ends. If the
path in a barbell is trivial, the barbell is called a short barbell;
otherwise, it is a long barbell. A balanced circuit or a barbell is called a
sign-circuit of a signed graph. A sign-circuit cover $\mathcal{F}$ of a signed
graph is a family of sign-circuits which covers all edges of $(G,\sigma)$. In
fact, it is well-known that a signed graph has a sign-circuit cover if and
only if each edge lies in a sign-circuit, which is equivalent to the fact that
the signed graph admits a nowhere-zero integer flow, so-called, flow-
admissible. (Readers may refer to [2] for details). The shortest length of a
sign-circuit cover of a signed graph $(G,\sigma)$ is also denoted by $scc(G)$.
The shortest sign-circuit cover problem was initiated by
Má$\check{\text{c}}$ajová, Raspaud, Rollová, and Škoviera [5] and received
many attentions in recent years. It is a major open problem for the optimal
upper bound of shortest sign-circuit cover in signed graphs.

######  Problem 1.3.

What is the optimal constant $c$ such that $scc(G)\leq c\cdot|E(G)|$ for every
flow-admissible signed graph $(G,\sigma)$ ?

As remarked in [5], the signed Petersen graph $(P,\sigma)$ whose negative
edges induce a circuit of length five has $scc(P)=\frac{5}{3}|E(P)|$, which
indicates $c\geq\frac{5}{3}$. We list some of known results related to Problem
1.3.

  * (1)

$c\leq 11$ by Má$\check{\text{c}}$ajová, Raspaud, Rollová, and Škoviera [5].

  * (2)

$c\leq\frac{14}{3}$ by Lu, Cheng, Luo, and Zhang [15].

  * (3)

$c\leq\frac{25}{6}$ by Chen and Fan [17].

  * (4)

$c\leq\frac{11}{3}$ by Kaiser, Lukoťka, Má$\check{\text{c}}$ajová, and Rollová
[18].

  * (5)

$c\leq\frac{19}{6}$ by Wu and Ye [21].

For any flow-admissible $2$-edge-connected cubic signed graph $(G,\sigma)$, Wu
and Ye [22] obtained a better upper bound that $scc(G)\leq\frac{26}{9}|E(G)|$.
In this article, we focus on the shortest sign-circuit cover of 3-edge
colorable cubic signed graphs and prove the following theorem.

######  Theorem 1.4.

Every flow-admissible $3$-edge colorable cubic signed graph $(G,\sigma)$ has a
sign-circuit cover with length at most $\frac{20}{9}|E(G)|$.

An equivalent version of the Four-Color Theorem states that every $2$-edge-
connected cubic planar graph is $3$-edge colorable. So we have the following
corollary.

######  Corollary 1.5.

Every flow-admissible $2$-edge-connected cubic planar signed graph
$(G,\sigma)$ has a sign-circuit cover with length at most
$\frac{20}{9}|E(G)|$.

Now we introduce more notation and terminologies used in the following
sections. Let $G$ be a graph and $T\subseteq V(G)$ with $|T|\equiv 0\pmod{2}$.
A $T$-join $J$ of $G$ with respect to $T$ is a subset of edges of $G$ such
that $d_{J}(v)\equiv 1\pmod{2}$ if and only if $v\in T$, where $d_{J}(v)$
denotes the degree of $v$ in the edge-induced subgraph $G[J]$. A $T$-join is
minimum if it has minimum number of edges among all $T$-joins. Let
$G^{\prime}$ be the graph obtained from a graph $G$ by deleting all the
bridges of $G$. Then the components of $G^{\prime}$ are called the bridgeless-
blocks of $G$. By the definition, a bridgeless-block is either a single vertex
or a maximal $2$-edge-connected subgraph of $G$. For a vertex subset
$U\subseteq V(G)$, $\delta_{G}(U)$ denotes the set of edges with one end in
$U$ and the other in $V(G)\setminus U$. Let $u$, $v$ be two vertices in
$V(G)$. A $(u,v)$-path is a path connecting $u$ and $v$. Let $C=v_{1}\ldots
v_{r}v_{1}$ be a circuit where $v_{1},v_{2},\ldots,v_{r}$ appear in clockwise
on $C$. A segment of $C$ is the path $v_{i}v_{i+1}\ldots v_{j-1}v_{j}$ (where
the sum of the index is under modulo $r$) contained in $C$ and is denoted by
$v_{i}Cv_{j}$. A connected graph $H$ is called a cycle-tree [22] if it has no
vertices of degree 1 and all circuits of $H$ are edge-disjoint. In a signed
graph, switching a vertex $u$ means reversing the signs of all edges incident
with $u$. Two signed graphs are equivalent if one can be obtained from the
other by a sequence of switching operations, and a signed graph is balanced if
and only if it is equivalent to an ordinary graph. The set of negative edges
of $(G,\sigma)$ is denoted by $E_{N}(G,\sigma)$.

The rest of the article is organized as follows. Some basic lemmas about
signed graph and $T$-join and a crucial lemma which deals with a special case
in our proof are given in Section 2. Then we are able to complete the proof of
Theorem 1.4 in Section 3 and we will finish with some discussions and remark.

##  2 Some Lemmas

The following lemma due to Bouchet [2] characterized connected flow-admissible
signed graphs.

######  Lemma 2.1 (Bouchet [2]).

A connected signed graph $(G,\sigma)$ is flow-admissible if and only if it is
not equivalent to a signed graph with exactly one negative edge and it has no
bridge $e$ such that $(G-e,\sigma|_{G-e})$ has a balanced component.

######  Lemma 2.2 (Li, Li, Luo, Zhang and Zhang [7]).

Let $T$ be a spanning tree of a signed graph $G$. For every $e\notin E(T)$,
let $C_{e}$ be the unique circuit contained in $T+e$. If the circuit $C_{e}$
is balanced for every $e\notin E(T)$, then $G$ is balanced.

Wu and Ye [21] gave a lemma to control the size of a $T$-join.

######  Lemma 2.3 (Wu and Ye [21]).

Let $G$ be a 2-edge-connected graph and $T$ be subset of vertices with $|T|$
even. Then $G$ has a $T$-join of size at most $\frac{1}{2}|E(G)|$.

The following two results gave upper bounds of $scc(G)$ with $G$ under some
constrains.

######  Lemma 2.4 (Chen, Fan [3] and Kaiser, Lukoťka,
Má$\check{\text{c}}$ajová, Rollová [18]).

Let $(G,\sigma)$ be a signed graph and suppose that each bridgeless-block of
$G$ is Eulerian.

(a)(Corollary 1.5 in [3]) If $(G,\sigma)$ is flow-admissible, then
$scc(G)\leq\frac{3}{2}|E(G)|$.

(b)(Corollary 2.6 in [18]) If the union of all the bridgeless-block of $G$,
denoted by $H$, is positive, then there exists a family of sign-circuits
${\mathcal{F}}$ covers $H$ with length at most $\frac{4}{3}|E(G)|$.

A combination of the above two lemmas leads to the following.

######  Lemma 2.5.

Let $F$ be a $2$-factor of a $2$-edge-connected cubic sign graph $(G,\sigma)$.
If $F$ contains even number of negative edges, then there exists a family of
sign-circuits ${\mathcal{F}}$ covers $F$ with length at most
$\frac{10}{9}|E(G)|$.

###### Proof.

We may assume that the $2$-factor $F$ consists of circuits
$C_{1},C_{2},\ldots,C_{t}$. Denote by $G^{*}$ the graph obtained from $G$ by
contracting each circuit $C_{i}$ of $F$ to a single vertex $c_{i}$.

Since $F$ contains even number of negative edges, the number of unbalanced
circuits in $F$ is even. Without loss of generality, we may assume that
$\mathcal{C}=\\{C_{1},C_{2},...,C_{2s}\\}$ is the set of unbalanced circuits
of $F$. Let $T=\\{c_{1},c_{2},...,c_{2s}\\}$ and $J$ be a minimum $T$-join of
$G^{*}$ with respect to $T$. Since $G$ is 2-edge-connected and $G^{*}$ is
obtained from $G$ by contracting edges, $G^{*}$ is 2-edge-connected as well.
By Lemma 2.3, we have $|J|\leq\frac{1}{2}|E(G^{*})|=\frac{1}{6}|E(G)|$.
Consider the edge set $F\cup J$ in $G$, and we view it as an edge-induced
subgraph of $G$. By the definition of $T$-join, we can apply Lemma 2.4(b) to
$F\cup J$, i.e., there exists a family of sign-circuits ${\mathcal{F}}$ covers
$F$ with length

$\displaystyle\ell({\mathcal{F}})$ $\displaystyle\leq\frac{4}{3}|E(F\cup J)|$
$\displaystyle=\frac{4}{3}\left(|E(F)|+|E(J)|\right)$
$\displaystyle\leq\frac{4}{3}\left(\frac{2}{3}|E(G)|+\frac{1}{6}|E(G)|\right)$
$\displaystyle=\frac{10}{9}|E(G)|.$

This proves the lemma. ∎

The proof of the following lemma is inspired by the proof of Lemma 3.7 in [7]
on flows of $3$-edge colorable cubic signed graphs.

######  Lemma 2.6.

Let $C$ be an unbalanced circuit of a cubic signed graph $(G,\sigma)$. If
$(G,\sigma)$ is flow-admissible and $G-E(C)$ is balanced, then $(G,\sigma)$
has a family $\mathcal{F}$ of sign-circuits such that

(1) $E(C)$ is covered by $\mathcal{F}$, and

(2) the length of $\mathcal{F}$ satisfies
$\ell(\mathcal{F})\leq\frac{8}{9}|E(G)|+|E(C)|$.

###### Proof.

Let $G^{\prime}=G-E(C)$. Since $G^{\prime}$ is balanced, with some switching
operations, we may assume that all edges in $E(G^{\prime})$ are positive and
thus $E_{N}(G,\sigma)\subseteq E(C)$.

Let $M$ be a component of $G^{\prime}$. The circuit $C$ was divided by the
vertices of $M$ into pairwise edge-disjoint paths (called segments) whose end-
vertices lie in $M$ and all inner vertices lie in $C$. An end-vertex of a
segment is called an attachment of $M$. A segment is called positive
(negative, resp.) if it contains an even (odd, resp.) number of negative
edges. Note that $M\cup S$ is unbalanced (balanced, resp.) if and only if the
segment $S$ is negative (positive, resp.). Since $M\cup C$ is unbalanced, the
number of negative segments determined by $M$ is odd.

Case 1. There exists a component $M$ of $G^{\prime}$ that determines more than
one negative segments.

Then in this case $M$ determines at least three negative segments and so
$|E(C)|\geq 3$. Let $u_{1}Cv_{1},u_{2}Cv_{2},u_{3}Cv_{3}$ be three consecutive
negative segments (in clockwise order) where $u_{i}$ and $v_{i}$ are
attachments for $i=1,2,3$. Then $v_{1}Cu_{2},v_{2}Cu_{3},v_{3}Cu_{1}$, where
each of them contains even number of negative edges. This implies that $C$ can
be partitioned into three pieces: $u_{1}Cu_{2},u_{2}Cu_{3}$, and $u_{3}Cu_{1}$
all contain odd number of negative edges. Note that $u_{i}$ and $u_{j}$ are
not adjacent in $C$ for distinct $i,j\in\\{1,2,3\\}$ since $G$ is cubic. Let
$P_{1}$ be a $(u_{1},u_{2})$-path in $M$. Since $M$ is connected, there is a
path $P_{2}$ from $u_{3}$ to $P_{1}$ such that $|V(P_{2})\cap V(P_{1})|=1$.
Let $v$ be the only common vertex in $P_{1}$ and $P_{2}$. Then $C,P_{1},P_{2}$
form a signed graph $H_{1}$ as illustrated in Figure 1.

Figure 1: $H_{1}=C\cup P_{11}\cup P_{12}\cup P_{2}$, negative segments are
dashed.

Note that $|E(H_{1})|\leq\frac{2}{3}|E(G)|+2$ since $G$ is cubic and there are
exactly four vertices of degree $3$ in $H_{1}$. Divide $P_{1}$ into two pieces
in $M$: $u_{1}P_{11}v$ and $vP_{12}u_{2}$, denote by $B_{1}=u_{1}P_{11}v\cup
vP_{12}u_{2}\cup u_{2}Cu_{1},B_{2}=u_{3}P_{2}v\cup vP_{11}u_{1}\cup
u_{1}Cu_{3},B_{3}=u_{2}P_{12}v\cup vP_{2}u_{3}\cup u_{3}Cu_{2}$. Note that
each of $u_{2}Cu_{1},u_{1}Cu_{3},u_{3}Cu_{2}$ contains even number of negative
edges. So $B_{1},B_{2},B_{3}$ are all balanced circuits and
$\mathcal{F}_{1}=\\{B_{1},B_{2}\\}$, $\mathcal{F}_{2}=\\{B_{2},B_{3}\\}$,
$\mathcal{F}_{3}=\\{B_{3},B_{1}\\}$ are all sign-circuit covers of $H_{1}$,
which are also sign-circuit covers of $C$ since $E(C)\subset E(H_{1})$. Note
that $\mathcal{F}=\\{\mathcal{F}_{1},\mathcal{F}_{2},\mathcal{F}_{3}\\}$
covers edge edge of $H_{1}$ exactly $4$ times. So we have

$\displaystyle\min\\{\ell(\mathcal{F}_{1}),\ell(\mathcal{F}_{2}),\ell(\mathcal{F}_{3})\\}$
$\displaystyle\leq\frac{1}{3}\left(\ell(\mathcal{F}_{1})+\ell(\mathcal{F}_{2})+\ell(\mathcal{F}_{3})\right)$
$\displaystyle=\frac{4}{3}|E(H_{1})|$
$\displaystyle\leq\frac{4}{3}\left(\frac{2}{3}|E(G)|+2\right)$
$\displaystyle<\frac{8}{9}|E(G)|+|E(C)|.$

Case 2. Each component of $G^{\prime}$ determines exactly one negative
segment.

Let $\mathcal{M}$ denote the set of all components of $G^{\prime}$. For each
component $M$, denote by $S_{M}=uCv$ the negative segment determined by $M$
where $u$ and $v$ are two attachments of $M$ on $C$. Denote by
$S^{\prime}_{M}=vCu$ the cosegment of $S_{M}$, which is the complement of
$S_{M}$ on $C$. Then $E(S_{M})\neq\emptyset$ and
$S^{\prime}_{M}=E(C)-E(S_{M})$. We have the following two conclusions:

######  Claim 1 (see Claim 3.7.2 in [7]).

$\cap_{M\in\mathcal{M}}E(S_{M})=\emptyset,$

or equivalently, $\cup_{M\in\mathcal{M}}E(S^{\prime}_{M})=C$ and
$|\mathcal{M}|\geq 2$.

Let $\mathcal{S}=\\{S^{\prime}_{1},S^{\prime}_{2},...,S^{\prime}_{t}\\}$ be a
minimal cosegment cover of $C$. We have

######  Claim 2 (see Claim 3.7.3 in [7]).

For any edge $e\in E(C)$, $e$ is contained in at most two cosegments.

###### Proof Sketches of Claims 1 and 2:.

For the sake of completeness, we present the proof sketches of this two claims
here. Suppose to the contrary $\cap_{M\in\mathcal{M}}E(S_{M})\neq\emptyset$
and $e^{*}\in\cap_{M\in\mathcal{M}}E(S_{M}).$ Then there is a spanning tree
$T$ of $G-e^{*}$ containing the path $P^{*}=C-e^{*}$. Let $e=uv\in
E(G)-e^{*}-E(T)$. Denote the unique circuit contained in $T+e$ by $C_{e}$.

If $E(C_{e})\cap E(P^{*})=\emptyset$, then $C_{e}$ contains no negative edges
and thus is balanced. Otherwise since $T$ contains all the edges in $C-e^{*}$,
$E(C_{e})\cap E(C)$ is a path $P$ on $C$. let $u^{\prime}$ and $v^{\prime}$ be
the two end-vertices of $P$ in clockwise order on $C.$ Then
$C_{e}-V(P)+{u^{\prime},v^{\prime}}$ is a also a path and thus it is contained
in some component $M\in\mathcal{M}.$ This implies that $u^{\prime}$ and
$v^{\prime}$ are two attachments of $M$ on $C.$ Since $e^{*}$ belongs to the
only negative segment of $C$ determined by $M$, ${u^{\prime}Cv^{\prime}}$ is
the union of some positive segments of $C$ determined by $M$. Therefore
$C_{e}$ has an even number of negative edges and thus is balanced. By Lemma
2.2, $G-e^{*}$ is balanced, contradicting Lemma 2.1. This proves
$\cap_{M\in\mathcal{M}}E(S_{M})=\emptyset$. Since
$E(S^{\prime}_{M})=E(C)-E(S_{M})$ and
$\cap_{M\in\mathcal{M}}E(S_{M})=\emptyset$, we have
$\cup_{M\in\mathcal{M}}E(S^{\prime}_{M})=C$. Since $E(S_{M})\neq\emptyset$ and
$\cap_{M\in\mathcal{M}}E(S_{M})=\emptyset$, we have $|\mathcal{M}|\geq 2$.
This completes the proof of the claim 1.

Suppose to the contrary that there exists an edge $e=uv$ that belongs to three
cosegments $L_{1},L_{2},L_{3}$ of $\mathcal{S}$. Denote $L_{i}=u_{i}Cv_{i}$
for each $i=1,2,3$. Without loss of generality, we may assume that $u_{2}$
belongs to $u_{1}Cu$. Then $v_{2}$ doesn’t belong to $u_{1}Cv_{1}$ (see Figure
2). Note that $v_{3}$ belongs to $u_{1}Cu_{3}$. If $u_{3}$ belongs to
$u_{1}Cu$, then both $v_{3}$ and $u_{3}$ belongs to $u_{1}Cv_{1}$ and thus
$L_{1}\cup L_{3}=C$ (see Figure 2-(a)), contradicting the minimality of
$\mathcal{S}$. If $u_{3}$ doesn’t belong to $u_{1}Cu$, then $u_{3}$ belongs to
$vCv_{2}$. Since $L_{3}$ contains $uv$, $v_{3}$ belongs to $vCv_{2}$. Thus
both $v_{3}$ and $u_{3}$ belongs to $u_{2}Cv_{2}$. Therefore $L_{2}\cup
L_{3}=C$ (see Figure 2-(b)), also contradicting the minimality of
$\mathcal{S}$. This completes the proof of the claim 2. ∎

Figure 2: Three cosegments sharing an edge.

For each $i=1,...,t$, denote by $S^{\prime}_{i}=x_{i}Cy_{i}$ and let $P_{i}$
be a path in $M_{i}$ connecting $x_{i}$ and $y_{i}$. Then
$C_{i}=S^{\prime}_{i}\cup P_{i}$ is a balanced Eulerian subgraph. By Claims 1
and 2, we may assume that the vertices
$x_{1},y_{t},x_{2},y_{1},...,x_{t},y_{t-1},x_{1}$ appear on $C$ in clockwise
order. Then $C_{i}\cap C_{j}\neq\emptyset$ if and only if $|j-i|\equiv
1\pmod{t}$. Moreover $|C_{i}\cap C_{i+1}|=x_{i+1}Cy_{i}$, where the sum of the
indices are taken modulo $t$. See Figure 3 for an illustration with $t=5$.

Figure 3: Minimal cosegment cover of $C$ with $t=5$.

Let $H_{2}=C\cup P_{1}\cup P_{2}\cup...\cup P_{t}$ and $B_{i}=x_{i}Cy_{i}\cup
y_{i}P_{i}x_{i}$ for $i=1,2,...,t$. Note that $B_{i}$ is a balanced circuit
and so $\mathcal{F}=\\{B_{1},B_{2},...,B_{t}\\}$ is a sign-circuit cover of
$C$. Obviously, $|E(H_{2})|\leq\frac{2}{3}|E(G)|+t$ since $G$ is cubic and
there are exactly $2t$ vertices of degree $3$ in $H_{2}$. By Claim 2,
$\mathcal{F}$ covers the edges in $C$ at most twice and edges in
$P_{1}\cup\ldots\cup P_{t}$ exactly once. Let $W$ be the set of edges covered
by $\mathcal{F}$ twice. Then $W\subset E(C)$. Since $G$ is cubic, $x_{i}\neq
y_{j}$ for all $i,j\in\\{1,2,...,t\\}$. So we have $|W|\leq|E(C)|-t$.
Therefore,

$\displaystyle\ell(\mathcal{F})$
$\displaystyle=|E(B_{1})|+|E(B_{2})|+...+|E(B_{t})|$
$\displaystyle\leq|E(H_{2})|+|E(C)|-t$
$\displaystyle\leq\frac{2}{3}|E(G)|+t+|E(C)|-t$
$\displaystyle\leq\frac{8}{9}|E(G)|+|E(C)|.$

This completes the proof. ∎

##  3 Proof of Theorem 1.4

###### Proof of Theorem 1.4.

Let $f$ be a 3-edge coloring of connected cubic graph $G$. Let $R,B,Y$ be the
three color classes of $f$. Recall that $E_{N}(G,\sigma)$ is the set of
negative edges in $(G,\sigma)$. Without loss of generality, we may assume
$\left|R\cap E_{N}(G,\sigma)\right|\equiv\left|B\cap
E_{N}(G,\sigma)\right|\pmod{2}.$ Denote by $M_{1}M_{2}$ the $2$-factor induced
by $M_{1}\cup M_{2}$ for each pair $M_{1},M_{2}\in\\{R,B,Y\\}$. Since $|R\cap
E_{N}(G,\sigma)|\equiv|B\cap E_{N}(G,\sigma)|\pmod{2}$, $RB$ has an even
number of unbalanced components. By Lemma 2.5, there exists a family of sign-
circuits ${\mathcal{F}}_{1}$ covers $RB$ with length at most
$\frac{10}{9}|E(G)|$.

Case 1. $RB$ contains an unbalanced circuit.

First, assume that $|Y\cap E_{N}(G,\sigma)|$ has the same parity with $|R\cap
E_{N}(G,\sigma)|$. Then $RY$ has an even number of unbalanced circuits. By
Lemma 2.5, we can find a family of sign-circuits ${\mathcal{F}}_{2}$ covers
$RY$ with length at most $\frac{10}{9}|E(G)|$. Therefore,
$\mathcal{F}={\mathcal{F}}_{1}\cup{\mathcal{F}}_{2}$ is a sign-circuit cover
of $G$ with length

$\displaystyle\ell(\mathcal{F})=\ell({\mathcal{F}}_{1})+\ell({\mathcal{F}}_{2})\leq\frac{10}{9}|E(G)|+\frac{10}{9}|E(G)|=\frac{20}{9}|E(G)|.$

Then, assume instead that $|Y\cap E_{N}(G,\sigma)|$ has different parity with
$|R\cap E_{N}(G,\sigma)|$. Let $C$ be an unbalanced circuit in $RB$. Now we
swap the colors $R$ and $B$ on $C$, i.e. reset $R^{\prime}=R\triangle E(C)$
and $B^{\prime}=B\triangle E(C)$ respectively. Note that the operation will
change the parity of $|R\cap E_{N}(G,\sigma)|$ and $|B\cap E_{N}(G,\sigma)|$.
This implies that $|Y\cap E_{N}(G,\sigma)|\equiv|R^{\prime}\cap
E_{N}(G,\sigma)|\equiv|B^{\prime}\cap E_{N}(G,\sigma)|\pmod{2}$ now. So,
similar as the previous paragraph, we apply Lemma 2.5 to find a family of
sign-circuits ${\mathcal{F}}_{2}^{\prime}$ covers $R^{\prime}Y$ with length at
most $\frac{10}{9}|E(G)|$. Notice that ${\mathcal{F}}_{1}$ covers
$RB=R^{\prime}B^{\prime}$ with length at most $\frac{10}{9}|E(G)|$. Hence
$\mathcal{F}={\mathcal{F}}_{1}\cup{\mathcal{F}}_{2}^{\prime}$ is a sign-
circuit cover of $G$ with length at most $\frac{20}{9}|E(G)|$.

$RB$ contains no unbalanced circuit.

In this case, each circuit $C_{i}$ of $RB$ is a balanced circuit. Let
${\mathcal{F}}_{1}=\\{C_{i}|C_{i}$ is a balanced circuit of $RB\\}$. Then
${\mathcal{F}}_{1}$ is a family of sign-circuits covering $RB$ with length
$\ell(\mathcal{F}_{1})=E(RB)=\frac{2}{3}|E(G)|$.

Subcase 2.1: The number of unbalanced circuits in $RY$ or $BY$ is even.

By Lemma 2.5, we have a family of sign-circuits ${\mathcal{F}}_{2}$ which
covers $RY$ or $BY$ with length at most $\frac{10}{9}|E(G)|$. Therefore
$\mathcal{F}={\mathcal{F}}_{1}\cup{\mathcal{F}}_{2}$ is a sign-circuit cover
of $G$ with length $\ell(\mathcal{F})\leq\frac{16}{9}|E(G)|$.

Subcase 2.2: The number of unbalanced circuits in $RY$ or $BY$ is equal to
one.

Without loss of generality, assume that $RY$ has exactly one unbalanced
component, say, $C_{1}$. Let $\mathcal{C}=\\{C_{1},...,C_{m}\\}$ be the set of
components of $RY$, where each $C_{i}\,(i\geq 2)$ is balanced. Let
${\mathcal{F}}_{2}=\\{C_{i}:i\geq 2\\}$. Then ${\mathcal{F}}_{2}$ is a family
of sign-circuits covering $RY-E(C_{1})$ with length
$\frac{2}{3}|E(G)|-|E(C_{1})|$. We consider the following two cases in order
to cover $C_{1}$.

Assume first that $G$ contains an unbalanced circuit $C^{\prime}$ with
$E(C^{\prime})\cap E(C_{1})=\emptyset$. Since $G$ is cubic and connected,
there is a long barbell $Q$ in $G$ with $P$ as the path connecting $C_{1}$ and
$C^{\prime}$ with $|E(Q)\leq\frac{2}{3}|E(G)|+1$. Therefore,
$\mathcal{F}={\mathcal{F}}_{1}\cup{\mathcal{F}}_{2}\cup Q$ is a sign-circuit
cover of $G$ with length

$\displaystyle\ell(\mathcal{F})$
$\displaystyle=\ell({\mathcal{F}}_{1})+\ell({\mathcal{F}}_{2})+\ell(Q)$
$\displaystyle\leq\frac{2}{3}|E(G)|+\frac{2}{3}|E(G)|-|E(C_{1})|+\frac{2}{3}|E(G)|+1$
$\displaystyle<2|E(G)|.$

Then assume instead that $G$ contains no unbalanced circuit $C^{\prime}$ with
$E(C^{\prime})\cap E(C_{1})=\emptyset$. In this case, $G-E(C_{1})$ is
balanced. By Lemma 2.6, there exists a family ${\mathcal{F}}_{3}$ of sign-
circuits covering $E(C_{1})$ with length at most
$\frac{8}{9}|E(G)|+|E(C_{1})|$. Therefore,
$\mathcal{F}={\mathcal{F}}_{1}\cup{\mathcal{F}}_{2}\cup{\mathcal{F}}_{3}$ is a
sign-circuit cover of $G$ with length

$\displaystyle\ell(\mathcal{F})$
$\displaystyle=\ell({\mathcal{F}}_{1})+\ell({\mathcal{F}}_{2})+\ell({\mathcal{F}}_{3})$
$\displaystyle\leq\frac{2}{3}|E(G)|+\frac{2}{3}|E(G)|-|E(C_{1})|+\frac{8}{9}|E(G)|+|E(C_{1})|$
$\displaystyle\leq\frac{20}{9}|E(G)|.$

Subcase 2.3: The number of unbalanced circuits in each of $RY$, $BY$ is odd
and is at least $3$.

Let $\mathcal{C}=\\{C_{1},...,C_{m}\\}$ be the set of components of $RY$.
Denote by $G^{*}$ the graph obtained from $G$ by contracting each circuit
$C_{i}$ of $RY$ to a single vertex $u_{i}$, where $i=1,2,...,m$. Note that
$G^{*}$ is connected, and so let $T^{*}$ be a spanning tree of $G^{*}$. Then
$T^{*}\cup RY$ is a cycle-tree in $G$, denoted by $H$, containing at least $3$
unbalanced circuits. Let $B^{\prime}$ be the set of bridges of $H$ such that
$b_{i}\in B^{\prime}$ if and only if $(H-b_{i},\sigma|_{H-b_{i}})$ has a
balanced component $H_{i}$. $B=\emptyset$ if no such bridge exists in $H$. Let
$H^{\prime}=H-(B^{\prime}\cup(\cup_{i=1,...,|B^{\prime}|}E(H_{i}))$. Note that
$H^{\prime}$ contains all the unbalanced circuit of $\mathcal{C}$. By Lemmas
2.1 and 2.4(a), $H^{\prime}$ is flow-admissible and has a sign-circuit cover
${\mathcal{F}}_{2}$ with length at most $\frac{3}{2}|E(H^{\prime})|$. Since
the circuits in $H_{i}$ are all balanced circuits, we can cover them with
length at most
$|\cup_{i=1,...,|B^{\prime}|}E(H_{i})|\leq|E(H)|-|E(H^{\prime})|$. Thus we
have a sign-circuit cover $\mathcal{F}_{3}$ of $RY$ with length

$\displaystyle\ell(\mathcal{F}_{3})$
$\displaystyle=\ell(\mathcal{F}_{2})+(|E(H)|-|E(H^{\prime})|)$
$\displaystyle\leq\frac{3}{2}|E(H^{\prime})|+|E(H)|-|E(H^{\prime})|$
$\displaystyle\leq\frac{3}{2}|E(H)|<\frac{3}{2}|E(G)|.$

Therefore, $\mathcal{F}=\mathcal{F}_{1}\cup\mathcal{F}_{3}$ is a sign-circuit
cover of $G$ with length

$\displaystyle\ell(\mathcal{F})$
$\displaystyle=\ell(\mathcal{F}_{1})+\ell(\mathcal{F}_{3})$
$\displaystyle\leq\frac{2}{3}|E(G)|+\frac{3}{2}|E(G)|$
$\displaystyle=\frac{13}{6}|E(G)|<\frac{20}{9}|E(G)|.$

This completes the proof. ∎

Remark. The upper bound of $scc(G)$ in Theorem 1.4 seems not to be tight. We
realized that the 3-edge colorable cubic signed graph $(G,\sigma)$ as
illustrated in Figure 4 has a sign-circuit cover with length
$\frac{13}{9}|E(G)|$. The problem to determine the optimal upper bound for the
shortest sign-circuit cover of 3-edge colorable cubic signed graph remains
open.

Figure 4: $(G,\sigma)$ with a shortest circuit cover with length
$\frac{13}{9}|E(G)|$.

Data Availability: Data sharing not applicable to this article as no datasets
were generated or analysed during the current study.

## References

  * [1] Alon, N and Tarsi, M. Covering multigraphs by simple circuits. SIAM Journal on Algebraic Discrete Methods, 6(3):345–350, 1985.
  * [2] Bouchet, André. Nowhere-zero integral flows on a bidirected graph. Journal of Combinatorial Theory, Series B, 34(3):279–292, 1983.
  * [3] Chen, Jing and Fan, Genghua. Circuit k-covers of signed graphs. Discrete Applied Mathematics, 294:41–54, 2021.
  * [4] Hou, Xinmin and Zhang, Cun-Quan. A note on shortest cycle covers of cubic graphs. Journal of Graph Theory, 71(2):123–127, 2012.
  * [5] Máčajová, Edita and Raspaud, André and Rollová, Edita and Škoviera, Martin. Circuit covers of signed graphs. Journal of Graph Theory, 81(2):120–133, 2016.
  * [6] Máčajová, Edita and Raspaud, André and Tarsi, Michael and Zhu, Xuding. Short cycle covers of graphs and nowhere-zero flows. Journal of Graph Theory, 68(4):340–348, 2011.
  * [7] Li, Liangchen and Li, Chong and Luo, Rong and Zhang, Cun-Quan and Zhang, Hailiang. Flows of 3-edge colorable cubic signed graphs. preprint.
  * [8] Itai, Alon and Lipton, Richard J and Papadimitriou, Christos H and Rodeh, Michael. Covering graphs by simple circuits. SIAM Journal on Computing, 10(4):746–750, 1981.
  * [9] Thomassen, Carsten. On the complexity of finding a minimum cycle cover of a graph. SIAM Journal on Computing, 26(3):675–677, 1997.
  * [10] Jamshy, Ury and Tarsi, Michael. Short cycle covers and the cycle double cover conjecture. Journal of Combinatorial Theory, Series B, 56(2):197–204, 1992.
  * [11] Seymour, Paul D. Sums of circuits. Graph theory and related topics, 1:341–355, 1979.
  * [12] Szekeres, George. Polyhedral decompositions of cubic graphs. Bulletin of the Australian Mathematical Society, 8(3):367–387, 1973.
  * [13] Bermond, Jean Claude and Jackson, Bill and Jaeger, François. Shortest coverings of graphs with cycles. Journal of Combinatorial Theory, Series B, 35(3):297–308, 1983.
  * [14] Lukotka, Robert. Short cycle covers of cubic graphs and intersecting 5-circuits. SIAM Journal on Discrete Mathematics, 34(1) :188–211, 2020.
  * [15] Lu, You and Cheng, Jian and Luo, Rong and Zhang, Cun-Quan. Shortest circuit covers of signed graphs. Journal of Combinatorial Theory, Series B, 134:164–178, 2019.
  * [16] Fan, Genghua. Short cycle covers of cubic graphs. Journal of Graph Theory, 18(2):131–141, 1994.
  * [17] Chen, Jing and Fan, Genghua. Short signed circuit covers of signed graphs. Discrete Applied Mathematics, 235:51–58, 2018.
  * [18] Kaiser, Tomáš and Lukot’ka, Robert and Máčajová, Edita and Rollová, Edita. Shorter signed circuit covers of graphs. Journal of Graph Theory, 92(1):39–56, 2019.
  * [19] Jackson, Bill. Shortest circuit covers of cubic graphs. Journal of Combinatorial Theory, Series B, 60(2):299–307, 1994.
  * [20] Kaiser, Tomáš and Král’, Daniel and Lidickỳ, Bernard and Nejedlỳ, Pavel and Šámal, Robert. Short cycle covers of graphs with minimum degree three. SIAM Journal on Discrete Mathematics, 24(1):330–355 2010.
  * [21] Wu, Yezhou and Ye, Dong. Minimum T-joins and signed-circuit covering. SIAM Journal on Discrete Mathematics, 34(2):1192–1204, 2020.
  * [22] Wu, Yezhou and Ye, Dong. Circuit covers of cubic signed graphs. Journal of Graph Theory, 89(1):40–54, 2018.