Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4651650 | Electronic Notes in Discrete Mathematics | 2015 | 6 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics