A Faster Test for 4-Flow-Criticality in Snarks

No snark has a 4-flow. A snark G is 4-edge-critical (or 4-vertex-critical) if, for every edge e (or pair of vertices (u, v)) of G, the graph obtained after contracting e (or identifying u and v) has a 4-flow. It is known that to determine whether a graph has a 4-flow is an NP-complete problem. In this paper, we present an improved exponential time algorithm to check whether a snark is 4-edge-critical (or 4-vertex-critical) or not. The use of our algorithm allowed us to determine the number of 4-edge-critical and 4-vertex-critical snarks of order at most 36.