A strong snark is a 2-connected cubic graph which is not 3-edge-colourable and remains so after deleting any edge and suppressing the resulting 2-valent vertices. Strong snarks were introduced by Jaeger in 1985 as a class of cubic graphs that might include counterexamples to the cycle double cover conjecture, the 5-flow conjecture, or to other related longstanding conjectures. With these conjectures still widely open, strong snarks merit further investigation. In this paper we study colouring defect of strong snarks, an invariant introduced by Steffen in 2015 as the minimum number of edges of a cubic graph left uncovered by any set of three perfect matchings. This invariant provides one of measures of edge uncolourability of cubic graphs recently studied by several authors. Our main result shows that the colouring defect of a strong snark is at least 6, and that the bound is sharp.

A longstanding conjecture of Alon and Tarsi, and independly Jaeger (1985), suggests that the edges of every bridgeless graph can be covered with cycles of total length at most 7/5 • m , where m is the number of edges. We study the relationship between cycle covers and structural properties of cubic graphs, focusing on their colouring defect. This invariant, introduced by Steffen in 2015, is defined as the minimum number of edges left uncovered by any set of three perfect matchings of a cubic graph. We show that every bridgeless cubic graph with colouring defect not exceeding 3 admits a cycle cover of length at most 4/3 • m + 1, just one step above the universal lower bound of 4/3 • m for all cubic graphs. We also prove that, regardless of defect, the same bound holds for bridgeless cubic graphs that have an edge whose endvertices removed yield a 3-edge-colourable graph and the edge lies on a 5-cycle. Motivated by our investigations, we introduce a new invariant for cubic graphs, their covering excess, to measure the deviation of the length of a shortest cycle cover from the mentioned lower bound. Finally, we show that every bridgeless cubic graph with covering excess at most 1 admits a cycle double cover.

A permutation snark is a cubic graph which has a 2-factor consisting of two chordless cycles and is not 3-edge-colourable. The order of every permutation snark is twice an odd number, and thus it is an integer congruent to either 2 or 6 (mod 8). While there exist infinitely many permutation snarks whose orders cover all the integers congruent to 2 (mod 8), no permutation snarks of order 6 (mod 8) are known. Exhaustive computer searches (Brinkmann et al., 2013, and Goedgebeur and Renders, 2025) have revealed that if such a permutation snark exists, then its order must be at least 54. Brinkmann et al. (2013) also asked whether all permutation snarks have order 2 (mod 8). In this paper we relate the existence of permutation snarks of order 6 (mod 8) to the existence of noncritical permutations snarks, which are also unknown. Our main result states that if there exists a noncritical permutation snark, then there is also one on 6 (mod 8) vertices.

Abstract. We prove that a signed graph admits a nowhere-zero 8-flow, provided that it is flow-admissible and the underlying graph admits a nowhere-zero 4-flow. When combined with the 4-color theorem, this implies that every flow-admissible bridgeless planar signed graph admits a nowhere-zero 8-flow. Our result improves and generalizes previous results of Li et al. [ European J. Combin., 108 (2023), 103627], which state that every flow-admissible signed 3-edge-colorable cubic graph admits a nowhere-zero 10-flow and that every flow-admissible signed Hamiltonian graph admits a nowhere-zero 8-flow.

The resistance of a cubic graph is the smallest number of edges whose removal produces a 3-edge-colourable graph. The flow resistance is the minimum number of zeros in an integer 4-flow on the graph. Fiol et al. (2018) made a conjecture that the flow resistance of a bridgeless cubic graph never exceeds its resistance. The conjecture has recently been proved to be false by displaying a family of nontrivial snarks with resistance n and flow resistance 2n (Allie et al., 2022). In this paper, we strengthen the result by showing that the ratio of the flow resistance to the resistance of a snark can be arbitrarily large.

The perfect matching index of a cubic graph $G$, denoted by $\pi(G)$, is the smallest number of perfect matchings that cover all the edges of $G$. According to the Berge--Fulkerson conjecture, $\pi(G)\le5$ for every bridgeless cubic graph $G$. The class of graphs with $\pi\ge 5$ is of particular interest as many conjectures and open problems, including the famous cycle double cover conjecture, can be reduced to it. Although nontrivial examples of such graphs are very difficult to find, a few infinite families are known, all with circular flow number $\Phi_c(G)=5$. It has been therefore suggested [Abreu et al., Electron. J. Combin., 23 (2016), P3.54] that $\pi(G)\ge 5$ might imply $\Phi_c(G)\ge 5$. In this article we dispel these hopes and present a family of cyclically 4-edge-connected cubic graphs of girth at least 5 with $\pi\ge 5$ and $\Phi_c\le 4+\frac23$.

The well-known shortest cycle cover conjecture suggests that every bridgeless graph $G$ can have its edges covered with a collection of cycles of total length not exceeding $\frac75\cdot|E(G)|$. This conjecture is particularly interesting for cubic graphs, where the largest values of the ratio between the length of a shortest cycle cover and the number of edges are known. The covering ratio 7/5 is the best possible, being reached by the Petersen graph whose shortest cycle cover has length 21. There exist infinitely many cubic graphs with cyclic connectivity 2, as well as those with cyclic connectivity 3, whose covering ratio equals 7/5. By contrast, all cyclically 4-edge-connected cubic graphs where the length of a shortest cycle cover is known have covering ratio close to the natural lower bound which equals 4/3. In line with this observation, Brinkmannn et al. [ J. Combin. Theory Ser. B, 103 (2013), pp. 468--488] made a conjecture that every cyclically 4-edge-connected cubic graph has a cycle cover of length at most $\frac43 m+o(m)$, where $m$ is the number of edges. We disprove this conjecture by exhibiting an infinite family of cyclically 4-edge-connected cubic graphs $G_k$, $k\ge 2$, such that the length of a shortest cycle cover of each $G_k$ is at least $(\frac43 + \frac{1}{69})|E(G_k)|$.

We continue the study of circuit covers of signed graphs initiated by Máčajová et al. [ J. Graph Theory, 81 (2016), pp. 120--133] by investigating signed circuit covers of signed Eulerian graphs. A signed circuit cover of a signed graph is a collection of signed circuits such that each edge of the signed graph belongs to at least one of them. We prove that every signed Eulerian graph $G$ that admits a signed circuit cover has one of length at most $3/2\cdot|E(G)|$. We show that the bound is tight and characterize those graphs that reach it. This result stands in a sharp contrast with the unsigned case where the bound is $1\cdot|E(G)|$ (by the classical result of Veblen). For signed Eulerian graphs with an even number of negative edges we establish a better bound of $4/3\cdot|E(G)|$ and show that it is also tight.

We prove that an Eulerian graph $G$ admits a decomposition into $k$ closed trails of odd length if and only if and it contains at least $k$ pairwise edge-disjoint odd circuits and $k\equiv |E(G)|\pmod{2}$. We conjecture that a connected $2d$-regular graph of odd order with $d\ge 1$ admits a decomposition into $d$ odd closed trails sharing a common vertex and verify the conjecture for $d\le 3$. The case $d=3$ is crucial for determining the flow number of a signed Eulerian graph which is treated in a separate paper [E. Máčajová and M. Škoviera, SIAM J. Discrete Math., 31 (2017), pp. 1937-1952]. The proof of our conjecture for $d=3$ is surprisingly difficult and calls for the use of signed graphs as a convenient technical tool.

This paper is devoted to a detailed study of nowhere-zero flows on signed Eulerian graphs. We generalize the well-known fact about the existence of nowhere-zero 2-flows in Eulerian graphs by proving that every signed Eulerian graph that admits an integer nowhere-zero flow has a nowhere-zero 4-flow. We also characterize signed Eulerian graphs with flow number 2, 3, and 4, as well as those that do not have an integer nowhere-zero flow. Finally, we discuss the existence of nowhere-zero $A$-flows on signed Eulerian graphs for an arbitrary Abelian group $A$.