TY - JOUR
T1 - A Faster Test for 4-Flow-Criticality in Snarks
AU - Carneiro, André Breda
AU - da Silva, Cândida Nunes
AU - McKay, Brendan
N1 - Publisher Copyright:
© 2015 Elsevier B.V.
PY - 2015/12/1
Y1 - 2015/12/1
N2 - 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.
AB - 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.
KW - Nowhere-zero k-flows
KW - Snarks
KW - Tutte's Flow Conjectures
UR - http://www.scopus.com/inward/record.url?scp=84953390348&partnerID=8YFLogxK
U2 - 10.1016/j.endm.2015.07.033
DO - 10.1016/j.endm.2015.07.033
M3 - Article
SN - 1571-0653
VL - 50
SP - 193
EP - 198
JO - Electronic Notes in Discrete Mathematics
JF - Electronic Notes in Discrete Mathematics
ER -